Синтез автомата Мура по граф-схеме — различия между версиями
Строка 40: | Строка 40: | ||
Рис.1. ГСА автомата Мура с узлами. | Рис.1. ГСА автомата Мура с узлами. | ||
=== Разметка состояний === | === Разметка состояний === | ||
− | В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния b<sub>m</sub> в состояние b<sub>s</sub> — это переход из одной операторной вершины в другую при выполнении логический условий X(b<sub>m</sub>, b<sub>s</sub>) на пути из b<sub>m</sub> в b<sub>s</sub>. | + | В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния '''b<sub>m</sub>''' в состояние '''b<sub>s</sub>''' — это переход из одной операторной вершины в другую при выполнении логический условий '''X(b<sub>m</sub>,b<sub>s</sub>)''' на пути из '''b<sub>m</sub>''' в '''b<sub>s</sub>'''. |
Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b0. | Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b0. | ||
Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. | Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. | ||
Строка 56: | Строка 56: | ||
[[файл:ГСА013.png]] | [[файл:ГСА013.png]] | ||
− | В столбце X(b<sub>m</sub>,b<sub>s</sub>) единица записывается тогда, когда b<sub>m</sub> в b<sub>s</sub> переход осуществляется всегда. | + | В столбце '''X(b<sub>m</sub>,b<sub>s</sub>)''' единица записывается тогда, когда '''b<sub>m</sub>''' в '''b<sub>s</sub>''' переход осуществляется всегда. |
=== Кодирование состояний === | === Кодирование состояний === | ||
Произведём кодирование узлов (узлы ө не кодируются). | Произведём кодирование узлов (узлы ө не кодируются). | ||
− | В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на RS триггерах. | + | В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на '''RS''' триггерах. |
− | Коды состояний: k(b<sub>0</sub>)=000; k(b<sub>1</sub>)=001; k(b<sub>2</sub>)=010; k(b<sub>3</sub>)=011; k(b<sub>4</sub>)=100. | + | Коды состояний: '''k(b<sub>0</sub>)=000; k(b<sub>1</sub>)=001; k(b<sub>2</sub>)=010; k(b<sub>3</sub>)=011; k(b<sub>4</sub>)=100'''. |
=== Построение обратной структурной таблицы 2 === | === Построение обратной структурной таблицы 2 === | ||
Вначале описываем переходы в узлы, затем остальные переходы автомата. | Вначале описываем переходы в узлы, затем остальные переходы автомата. | ||
Строка 68: | Строка 68: | ||
[[файл:ГСА014.png]] | [[файл:ГСА014.png]] | ||
− | Если переход в некоторое состояние b<sub>s</sub> происходит из узла ө, то в автомате с памятью на RS триггерах значения R<sub>i</sub> и S<sub>i</sub> в обратной структурной таблице записываются с учетом кодов состояний b<sub>m</sub> из которых был переход в узел ө. | + | Если переход в некоторое состояние '''b<sub>s</sub>''' происходит из узла ө, то в автомате с памятью на '''RS''' триггерах значения '''R<sub>i</sub>''' и '''S<sub>i</sub>''' в обратной структурной таблице записываются с учетом кодов состояний '''b<sub>m</sub>''' из которых был переход в узел ө. |
[[файл:ГСА015.png]] | [[файл:ГСА015.png]] | ||
− | Рис.3. Схема определения значений R<sub>i</sub> и S<sub>i</sub>. | + | Рис.3. Схема определения значений '''R<sub>i</sub>''' и '''S<sub>i</sub>'''. |
=== Запись функции выходов и переходов автомата === | === Запись функции выходов и переходов автомата === | ||
− | По обратной структурной таблице запишем функции для ө, Y<sub>i</sub>, R<sub>i</sub> и S<sub>i</sub>. | + | По обратной структурной таблице запишем функции для '''ө, Y<sub>i</sub>, R<sub>i</sub>''' и '''S<sub>i</sub>'''. |
[[файл:ГСА016.png]] | [[файл:ГСА016.png]] | ||
Строка 90: | Строка 90: | ||
Рис.5. ГСА автомата Мура с узлами. | Рис.5. ГСА автомата Мура с узлами. | ||
=== Разметка состояний === | === Разметка состояний === | ||
− | В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния b<sub>m</sub> в состояние b<sub>s</sub> — это переход из одной операторной вершины в другую при выполнении логический условий X(b<sub>m</sub>, b<sub>s</sub>) на пути из b<sub>m</sub> в b<sub>s</sub>. | + | В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния '''b<sub>m</sub>''' в состояние '''b<sub>s</sub>''' — это переход из одной операторной вершины в другую при выполнении логический условий '''X(b<sub>m</sub>,b<sub>s</sub>)''' на пути из '''b<sub>m</sub>''' в '''b<sub>s</sub>'''. |
− | Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию | + | Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию '''b<sub>0</sub>'''. |
− | Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. | + | Узлы '''ө''' используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. |
[[файл:ГСА022.png]] | [[файл:ГСА022.png]] | ||
Строка 99: | Строка 99: | ||
=== Построение прямой таблицы переходов 3 === | === Построение прямой таблицы переходов 3 === | ||
Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: | Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: | ||
− | '''b<sub>m</sub>→b<sub>s</sub> | + | '''b<sub>m</sub>→b<sub>s</sub>, b<sub>m</sub>→ө<sub>s</sub>, ө<sub>m</sub>→b<sub>s</sub>, ө<sub>m</sub>→ө<sub>s</sub>'''. |
Все эти переходы описываются в прямой таблице переходов. | Все эти переходы описываются в прямой таблице переходов. | ||
Строка 106: | Строка 106: | ||
[[файл:ГСА023.png]] | [[файл:ГСА023.png]] | ||
− | В столбце X( | + | В столбце '''X(b<sub>m</sub>,b<sub>s</sub>)''' единица записывается тогда, когда '''b<sub>m</sub>''' в '''b<sub>s</sub>''' переход осуществляется всегда. |
=== Кодирование состояний === | === Кодирование состояний === | ||
Произведём кодирование узлов (узлы ө не кодируются). | Произведём кодирование узлов (узлы ө не кодируются). | ||
В данном примере — автомат имеет три состояния (кроме начального), для кодирования необходимо не менее двух двоичных разрядов. Память состояний на RS триггерах. | В данном примере — автомат имеет три состояния (кроме начального), для кодирования необходимо не менее двух двоичных разрядов. Память состояний на RS триггерах. | ||
− | Коды состояний: k(b<sub>0</sub>)=00; k(b<sub>1</sub>)=01; k(b<sub>2</sub>)=01; k(b<sub>3</sub>)=11. | + | Коды состояний: '''k(b<sub>0</sub>)=00; k(b<sub>1</sub>)=01; k(b<sub>2</sub>)=01; k(b<sub>3</sub>)=11'''. |
=== Построение обратной структурной таблицы 4 === | === Построение обратной структурной таблицы 4 === | ||
Вначале описываем переходы в узлы, затем остальные переходы автомата. | Вначале описываем переходы в узлы, затем остальные переходы автомата. | ||
Строка 118: | Строка 118: | ||
[[файл:ГСА024.png]] | [[файл:ГСА024.png]] | ||
− | Если переход в некоторое состояние b<sub>s</sub> происходит из узла ө, то в автомате с памятью на RS триггерах значения R<sub>i</sub> и S<sub>i</sub> в обратной структурной таблице записываются с | + | Если переход в некоторое состояние '''b<sub>s</sub>''' происходит из узла '''ө''', то в автомате с памятью на '''RS''' триггерах значения '''R<sub>i</sub>''' и '''S<sub>i</sub>''' в обратной структурной таблице записываются с учётом кодов состояний '''b<sub>m</sub>''' из которых был переход в узел '''ө'''. |
[[файл:ГСА025.png]] | [[файл:ГСА025.png]] | ||
− | Рис.7. Схема определения значений R<sub>i</sub> и S<sub>i</sub>. | + | Рис.7. Схема определения значений '''R<sub>i</sub>''' и '''S<sub>i</sub>'''. |
=== Запись функции выходов и переходов автомата === | === Запись функции выходов и переходов автомата === | ||
− | По обратной структурной таблице запишем функции для ө, Y<sub>i</sub>, R<sub>i</sub> и S<sub>i</sub>. | + | По обратной структурной таблице запишем функции для '''ө, Y<sub>i</sub>, R<sub>i</sub> и S<sub>i</sub>'''. |
[[файл:ГСА026.png]] | [[файл:ГСА026.png]] |
Версия 05:30, 9 июля 2022
Синтез автомата Мура по граф-схеме — это метод построения функциональной схемы автомата.
Содержание
Описание
Определение 1
Автомат Мура — абстрактный автомат второго рода — конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и, не зависит напрямую, в, отличие от автомата Мили, от входных значений. Автомат Мура назван в честь описавшего его свойства Эдварда Ф. Мура, опубликовавшего исследования в 1956 году в издании «Gedanken-experiments on Sequential Machines.».
Определение 2
Автомат Мура — кортеж из 6 элементов, включающий: множество внутренних состояний S (внутренний алфавит); начальное состояние S0; множество входных сигналов X (входной алфавит); множество выходных сигналов Y (выходной алфавит); функция переходов.
Обозначения
ГСА — граф-схема автомата;
ФСА — функциональная схема автомата;
b0 — операторная вершина — начальное и конечное состояние автомата;
bm — операторная вершина — исходное состояние перехода;
bs — операторная вершина — конечное состояние перехода;
өs — узел — дополнительная операторная вершина для упрощения ГСА;
bm→bs — переход из одной операторной вершины в другую;
bm→өs, өm→bs, өm→өs — дополнительные переходы;
X(bm, bs) — логическое условие перехода;
Si — значение на S-триггере;
Ri — значение на R-триггере.
Примеры:
Пример 1
Синтез автомата Мура по ГСА (рис.1).
Рис.1. ГСА автомата Мура с узлами.
Разметка состояний
В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния bm в состояние bs — это переход из одной операторной вершины в другую при выполнении логический условий X(bm,bs) на пути из bm в bs. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b0. Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются.
Рис.2. Размеченная ГСА автомата Мура с узлами.
Построение прямой таблицы переходов 1
Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: bm→bs, bm→өs, өm→bs, өm→өs. Все эти переходы описываются в прямой таблице переходов.
Таблица 1.
В столбце X(bm,bs) единица записывается тогда, когда bm в bs переход осуществляется всегда.
Кодирование состояний
Произведём кодирование узлов (узлы ө не кодируются). В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на RS триггерах. Коды состояний: k(b0)=000; k(b1)=001; k(b2)=010; k(b3)=011; k(b4)=100.
Построение обратной структурной таблицы 2
Вначале описываем переходы в узлы, затем остальные переходы автомата.
Таблица 2.
Если переход в некоторое состояние bs происходит из узла ө, то в автомате с памятью на RS триггерах значения Ri и Si в обратной структурной таблице записываются с учетом кодов состояний bm из которых был переход в узел ө.
Рис.3. Схема определения значений Ri и Si.
Запись функции выходов и переходов автомата
По обратной структурной таблице запишем функции для ө, Yi, Ri и Si.
Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов.
Построение ФСА автомата Мура
Рис.4. ФСА автомата Мура на жёсткой логике.
Пример 2
Синтез автомата Мура по ГСА (рис.5).
Рис.5. ГСА автомата Мура с узлами.
Разметка состояний
В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния bm в состояние bs — это переход из одной операторной вершины в другую при выполнении логический условий X(bm,bs) на пути из bm в bs. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b0. Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются.
Рис.6. Размеченная ГСА автомата Мура с узлами.
Построение прямой таблицы переходов 3
Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: bm→bs, bm→өs, өm→bs, өm→өs. Все эти переходы описываются в прямой таблице переходов.
Таблица 3.
В столбце X(bm,bs) единица записывается тогда, когда bm в bs переход осуществляется всегда.
Кодирование состояний
Произведём кодирование узлов (узлы ө не кодируются). В данном примере — автомат имеет три состояния (кроме начального), для кодирования необходимо не менее двух двоичных разрядов. Память состояний на RS триггерах. Коды состояний: k(b0)=00; k(b1)=01; k(b2)=01; k(b3)=11.
Построение обратной структурной таблицы 4
Вначале описываем переходы в узлы, затем остальные переходы автомата.
Таблица 4.
Если переход в некоторое состояние bs происходит из узла ө, то в автомате с памятью на RS триггерах значения Ri и Si в обратной структурной таблице записываются с учётом кодов состояний bm из которых был переход в узел ө.
Рис.7. Схема определения значений Ri и Si.
Запись функции выходов и переходов автомата
По обратной структурной таблице запишем функции для ө, Yi, Ri и Si.
Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов.
Построение ФСА автомата Мура
Рис.8. ФСА автомата Мура на жёсткой логике.
Ссылки
- Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г.
- Участник:Logic-samara