лр8. Построим комбинированную таблицу переходоввыходов
 Скачать 14.23 Kb.
|
|
построим комбинированную таблицу переходов/выходов Чтобы создать комбинированную таблицу переходов и выходов, нужно объединить информацию о переходах и выходах в одну таблицу. текующее состояние вход (A1) следующее состояние выход q1 a1 q3 1 q1 a2 q8 1 q3 a1 q1 1 q3 a2 q5 0 q8 a1 q5 0 q8 a2 q8 1 q5 a1 q4 1 q5 a2 q2 0 q2 a1 q4 1 q2 a2 q2 0 q4 a1 q1 1 q4 a2 q6 1 q6 a1 q3 1 q6 a2 q8 0 q7 a1 q4 1 q7 a2 q6 1 Определим последовательность состояний и выходное слово для произвольного входного слова из 10 символов Чтобы определить последовательность состояний и выходное слово для произвольного входного слова из 10 символов, нам нужно следовать правилам перехода, основанным на объединенной таблице. Давайте рассмотрим входное слово "a1 a2 a2 a1 a1 a1 a1 a2 a2 a2 a1". Начиная с начального состояния q1, мы можем проследить за переходами следующим образом: Ввод: a1 a2 a2 a1 a1 a1 a1 a2 a2 a2 a1 Шаг Ввод текущего состояния Вывод следующего состояния 1 a1 q1 q3 1 2 a2 q3 q5 0 3 a2 q5 q2 0 4 a1 q2 q4 1 5 a1 q4 q1 1 6 a1 q1 q3 1 7 a2 q3 q5 0 8 a2 q5 q2 0 9 a2 q2 q2 0 10 a1 q2 q4 1 Последовательность состояний такова: q1, q3, q5, q2, q4, q1, q3, q5, q2, q4. Соответствующим выходным словом является: 1 0 0 1 1 1 0 0 0 1. a1 q1 --------> q3 ---a1-- | / | | 1 / 0 | | / | a2| / a2 | a1 | / | v/ v q8 --------> q5 ---a1-- | / | | 0 / 1 | | / | a2| / a2 | a1 | / | v/ v q4 --------> q6 ---a1-- | / | | 1 / 1 | | / | a2| / a2 | a1 | / | v/ v q2 --------> q4 ---a1-- | / | | 1 / 1 | | / | a2| / a2 | a1 | / | v/ v q7 --------> q4 ---a1-- | | | 1 | | | a2| | a1 | | v v Мы можем преобразовать его в граф автомата Мура, удалив метки выходов из переходов и связав выходы с состояниями. Граф автомата Мура будет иметь вид: 1 0 1 0 0 q1 ---> q3 ---> q5 ---> q2 ---> q4 | / | / | / | | / | / | / | a2 a2 a2 a2 | \ | \ | \ | | \ | \ | \ | v v v v v v v q8 q5 q2 q4 q6 q4 q7 Таблица переходов для автомата Мура может быть построена на основе графика: текующее состояние ввод (A1) следующее состояние q1 a1 q3 q1 a2 q8 q3 a1 q5 q3 a2 q5 q8 a1 q5 q8 a2 q8 q5 a1 q2 q5 a2 q2 q2 a1 q4 q2 a2 q4 q4 a1 q1 q4 a2 q6 q6 a1 q3 q6 a2 q8 q7 a1 q4 q7 a2 q6 Используя таблицу переходов автомата Мура, мы можем определить выходное слово для входного слова "a1 a2 a2 a1 a1 a1 a2 a2 a2 a1". Мы начинаем с начального состояния q1 и следуем переходам, основанным на входном слове: Ввод: a1 a2 a2 a1 a1 a1 a1 a2 a2 a2 a1 Шаг Ввода текущего состояния Следующее состояние 1 a1 q1 q3 2 a2 q3 q5 3 a2 q5 q2 4 a1 q2 q4 5 a1 q4 q1 6 a1 q1 q3 7 a2 q3 q5 8 a2 q5 q2 9 a2 q2 q4 10 a1 q4 q1 Выходным словом для входного слова является: 1 0 0 1 1 1 0 0 0 1. Контрольные вопросы 1.Абстрактный автомат - это математическая модель, используемая для представления системы, которая может изменять свое внутреннее состояние на основе входных данных или событий. Он состоит из набора состояний, набора входных данных или событий, набора переходов, которые определяют изменения состояния, и, возможно, набора выходных данных. 2..Настройка конечного автомата относится к определению или конфигурированию его компонентов, таких как набор состояний, набор входных данных, правила перехода и выходные данные. Этот процесс определяет поведение и функциональность конечного автомата. 3.Способы настройки автоматов включают в себя: Определение набора состояний: укажите различные состояния, в которых может находиться автомат. Определение набора входных данных или событий: укажите возможные входные данные или события, которые могут инициировать переходы состояний. Настройка правил перехода: Определите, как автомат переходит из одного состояния в другое на основе входных данных. 4.Настройка выходных данных (в случае автоматов Мили и Мура): Связывайте выходные данные с определенными состояниями или переходами. Закон функционирования автомата Мили заключается в том, что он реагирует на входные данные путем перехода между состояниями и предоставления выходных данных на основе текущего состояния и комбинации входных данных. Выходные данные связаны с переходами между состояниями. 5.Закон функционирования автомата Мура аналогичен автомату Мили, но выходные данные связаны с отдельными состояниями, а не с переходами. Выходные данные зависят только от текущего состояния и не учитывают входные данные напрямую. 6.Разница между автоматом Мили и автоматом Мура заключается в ассоциации выходных данных. В автомате Мили выходные данные связаны с переходами, в то время как в автомате Мура выходные данные связаны с состояниями. 7.Разница между автоматом Мили и автоматом Мура заключается в том, что автомат Мили связывает выходные данные с переходами, в то время как автомат Мура связывает выходные данные с состояниями. 8.Примером графического способа настройки автомата Муки является представление его с помощью ориентированного графа, где состояния являются узлами, а переходы обозначены ребрами. Выходные данные могут быть связаны с переходами на графике. 9.Примером графического способа настройки автомата Мура также является представление его с помощью ориентированного графа, где состояния являются узлами, а переходы обозначены ребрами. Однако выходные данные связаны с состояниями на графике. 10.Таблица переходов автомата представляет собой табличное представление, которое показывает текущее состояние, входные данные и следующее состояние для каждой возможной комбинации. Он определяет поведение автомата на основе входных данных и текущего состояния. Пример таблицы выходных данных автомата Мили:| Current State | Input | Next State | Output | |---------------|-------|------------|--------| | q1 | a1 | q3 | 0 | | q1 | a2 | q8 | 1 | | q3 | a1 | q5 | 1 | | q3 | a2 | q5 | 0 | | q8 | a1 | q5 | 0 | | q8 | a2 | q8 | 1 | | q5 | a1 | q2 | 0 | | q5 | a2 | q2 | 1 | | q2 | a1 | q4 | 1 | | q2 | a2 | q4 | 0 | | q4 | a1 | q1 | 0 | | q4 | a2 | q6 Пример выходной таблицы автомата Мура: | State | Output | |-------|--------| | q1 | 0 | | q2 | 0 | | q3 | 1 | | q4 | 1 | | q5 | 0 | | q6 | 1 | | q7 | 0 | | q8 | 1 | Помеченная таблица переходов — это вариант таблицы переходов, в который включены дополнительные маркировки или метки для обозначения связанных выходов. Обычно используется для автомата Мили. |