Автомат Мура
Поделись знанием:
После своего свидания в Москве с Пьером князь Андреи уехал в Петербург по делам, как он сказал своим родным, но, в сущности, для того, чтобы встретить там князя Анатоля Курагина, которого он считал необходимым встретить. Курагина, о котором он осведомился, приехав в Петербург, уже там не было. Пьер дал знать своему шурину, что князь Андрей едет за ним. Анатоль Курагин тотчас получил назначение от военного министра и уехал в Молдавскую армию. В это же время в Петербурге князь Андрей встретил Кутузова, своего прежнего, всегда расположенного к нему, генерала, и Кутузов предложил ему ехать с ним вместе в Молдавскую армию, куда старый генерал назначался главнокомандующим. Князь Андрей, получив назначение состоять при штабе главной квартиры, уехал в Турцию.
Князь Андрей считал неудобным писать к Курагину и вызывать его. Не подав нового повода к дуэли, князь Андрей считал вызов с своей стороны компрометирующим графиню Ростову, и потому он искал личной встречи с Курагиным, в которой он намерен был найти новый повод к дуэли. Но в Турецкой армии ему также не удалось встретить Курагина, который вскоре после приезда князя Андрея в Турецкую армию вернулся в Россию. В новой стране и в новых условиях жизни князю Андрею стало жить легче. После измены своей невесты, которая тем сильнее поразила его, чем старательнее он скрывал ото всех произведенное на него действие, для него были тяжелы те условия жизни, в которых он был счастлив, и еще тяжелее были свобода и независимость, которыми он так дорожил прежде. Он не только не думал тех прежних мыслей, которые в первый раз пришли ему, глядя на небо на Аустерлицком поле, которые он любил развивать с Пьером и которые наполняли его уединение в Богучарове, а потом в Швейцарии и Риме; но он даже боялся вспоминать об этих мыслях, раскрывавших бесконечные и светлые горизонты. Его интересовали теперь только самые ближайшие, не связанные с прежними, практические интересы, за которые он ухватывался с тем большей жадностью, чем закрытое были от него прежние. Как будто тот бесконечный удаляющийся свод неба, стоявший прежде над ним, вдруг превратился в низкий, определенный, давивший его свод, в котором все было ясно, но ничего не было вечного и таинственного.
Из представлявшихся ему деятельностей военная служба была самая простая и знакомая ему. Состоя в должности дежурного генерала при штабе Кутузова, он упорно и усердно занимался делами, удивляя Кутузова своей охотой к работе и аккуратностью. Не найдя Курагина в Турции, князь Андрей не считал необходимым скакать за ним опять в Россию; но при всем том он знал, что, сколько бы ни прошло времени, он не мог, встретив Курагина, несмотря на все презрение, которое он имел к нему, несмотря на все доказательства, которые он делал себе, что ему не стоит унижаться до столкновения с ним, он знал, что, встретив его, он не мог не вызвать его, как не мог голодный человек не броситься на пищу. И это сознание того, что оскорбление еще не вымещено, что злоба не излита, а лежит на сердце, отравляло то искусственное спокойствие, которое в виде озабоченно хлопотливой и несколько честолюбивой и тщеславной деятельности устроил себе князь Андрей в Турции.
Автомат Мура (абстрактный автомат второго рода) в теории вычислений — конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван в честь описавшего его свойства Эдварда Ф. Мура, опубликовавшего исследования в 1956 году в издании «Gedanken-experiments on Sequential Machines.»[1]
Содержание
Формальное определение
Автомат Мура может быть определён как кортеж из 5 элементов, включающий:
- множество внутренних состояний S (внутренний алфавит);
- начальное состояние S0;
- множество входных сигналов X (входной алфавит);
- множество выходных сигналов Y (выходной алфавит);
- функция переходов Φ(z, x).
Для любого автомата Мура существует эквивалентный ему автомат Мили и наоборот. Любой автомат Мура путём добавления ряда внутренних состояний может быть преобразован в автомат Мили.
Способы задания
- Диаграмма — изображённый на плоскости ориентированный граф, вершины которого взаимно однозначно соответствуют состояниям автомата, а дуги — входным символам.
- Таблица переходов-выходов, в ячейках которой для каждой пары значений аргументов х(t), s(t) проставляются будущие внутренние состояния s(t+1). Значения выходных сигналов y(t) представляются в отдельном столбце.
Таблица переходов
| Y1 | Y2 | Y3 | Y1 | Y2 | Y2 | Y3 | |
|---|---|---|---|---|---|---|---|
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | |
| 1 | a5 | a4 | a5 | a3 | a4 | a2 | a5 |
| 2 | a7 | a1 | a4 | a2 | a1 | a3 | a4 |
См. также
- JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата
- Автомат Мура в сравнении с автоматом Мили
Напишите отзыв о статье "Автомат Мура"
Примечания
- ↑ Moore, Edward F (1956). «Gedanken-experiments on Sequential Machines». Automata Studies,Annals of Mathematical Studies (Princeton University Press) (34): 129–153.
Литература
- Karacuba A. A. Experimente mit Automaten (German) // Elektron. Inform.-verarb. Kybernetik, 11, 611—612 (1975). (нем.)
- Карацуба А. А. Решение одной задачи из теории конечных автоматов // УМН, т. 15, № 3(93), с. 157—159 (1960). (рус.)
- Карацуба А. А. [www.mi.ras.ru/~karatsuba/list.html Список научных трудов] (рус.)
- Karacuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975). (англ.)
- Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, N.J.(1956). (англ.)
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Автомат Мура
После своего свидания в Москве с Пьером князь Андреи уехал в Петербург по делам, как он сказал своим родным, но, в сущности, для того, чтобы встретить там князя Анатоля Курагина, которого он считал необходимым встретить. Курагина, о котором он осведомился, приехав в Петербург, уже там не было. Пьер дал знать своему шурину, что князь Андрей едет за ним. Анатоль Курагин тотчас получил назначение от военного министра и уехал в Молдавскую армию. В это же время в Петербурге князь Андрей встретил Кутузова, своего прежнего, всегда расположенного к нему, генерала, и Кутузов предложил ему ехать с ним вместе в Молдавскую армию, куда старый генерал назначался главнокомандующим. Князь Андрей, получив назначение состоять при штабе главной квартиры, уехал в Турцию.
Князь Андрей считал неудобным писать к Курагину и вызывать его. Не подав нового повода к дуэли, князь Андрей считал вызов с своей стороны компрометирующим графиню Ростову, и потому он искал личной встречи с Курагиным, в которой он намерен был найти новый повод к дуэли. Но в Турецкой армии ему также не удалось встретить Курагина, который вскоре после приезда князя Андрея в Турецкую армию вернулся в Россию. В новой стране и в новых условиях жизни князю Андрею стало жить легче. После измены своей невесты, которая тем сильнее поразила его, чем старательнее он скрывал ото всех произведенное на него действие, для него были тяжелы те условия жизни, в которых он был счастлив, и еще тяжелее были свобода и независимость, которыми он так дорожил прежде. Он не только не думал тех прежних мыслей, которые в первый раз пришли ему, глядя на небо на Аустерлицком поле, которые он любил развивать с Пьером и которые наполняли его уединение в Богучарове, а потом в Швейцарии и Риме; но он даже боялся вспоминать об этих мыслях, раскрывавших бесконечные и светлые горизонты. Его интересовали теперь только самые ближайшие, не связанные с прежними, практические интересы, за которые он ухватывался с тем большей жадностью, чем закрытое были от него прежние. Как будто тот бесконечный удаляющийся свод неба, стоявший прежде над ним, вдруг превратился в низкий, определенный, давивший его свод, в котором все было ясно, но ничего не было вечного и таинственного.
Из представлявшихся ему деятельностей военная служба была самая простая и знакомая ему. Состоя в должности дежурного генерала при штабе Кутузова, он упорно и усердно занимался делами, удивляя Кутузова своей охотой к работе и аккуратностью. Не найдя Курагина в Турции, князь Андрей не считал необходимым скакать за ним опять в Россию; но при всем том он знал, что, сколько бы ни прошло времени, он не мог, встретив Курагина, несмотря на все презрение, которое он имел к нему, несмотря на все доказательства, которые он делал себе, что ему не стоит унижаться до столкновения с ним, он знал, что, встретив его, он не мог не вызвать его, как не мог голодный человек не броситься на пищу. И это сознание того, что оскорбление еще не вымещено, что злоба не излита, а лежит на сердце, отравляло то искусственное спокойствие, которое в виде озабоченно хлопотливой и несколько честолюбивой и тщеславной деятельности устроил себе князь Андрей в Турции.
