Таблица - переход - автомат
Cтраница 1
Таблица переходов автомата Мура в общем случае может быть многозначной для нескольких входных векторов. Как частный случай, она может быть многозначной и для всех своих выходных векторов. И в этом случае восстановить автомат Мура возможно, ставя в соответствие каждому новому появившемуся состоянию конечный набор входных и выходных векторов. [1]
Правило построения таблицы переходов автомата состоит в следующем. [2]
Используя табл. III.5 и таблицу переходов автомата А ( табл. III.1), легко построить ( векторную) функцию возбуждения автомата А. Обозначим через х - ( х) внешний структурный входной сигнал автомата А; через v - ( PI I) - структурный выходной сигнал этого автомата, а через и ( ul иг) - структурный входной сигнал его памяти. [3]
Эти соотношения означают, что таблица переходов эквивалентного автомата Мили совпадает с таблицей переходов автомата Мура, а таблица выходов составляется так, что в каждую ее клетку записывается сигнал, которым отмечено состояние в данной клетке. При этом граф автомата Мили отличается только тем, что выходные сигналы из узлов графа перенесены на все ветви, входящие в данный узел. [4]
Второй шаг состоит в построении таблицы переходов искомого автомата А. При этом входными сигналами служат буквы исходного алфавита Ж, а внутренние состояния автомата отождествляются с множествами основных индексов. [5]
 |
Граф автомата Мили ( а и граф автомата Мура ( б. [6] |
В некоторых случаях оказывается удобным вместо таблицы переходов автоматов Мили и Мура использовать так называемую квадратную автоматную таблицу. Квадратной автоматной таблицей называется таблица, у которой строки и столбцы обозначены различными состояниями автомата. Xk, каждый из которых вызывает переход автомата из состояния Л / в состояние Л /, обозначается путем объединения сигналов знаком дизъюнкции: Х V з V V Xk. Для обозначения пустого множества может использоваться черточка. [7]
Производя перекодировку состояний и выходных букв, получаем отмеченную таблицу переходов автомата. [8]
При задании ( частичного) автомата А таблицами переводов и выходов таблица переходов автомата В получается прочеркиванием всех мест таблицы переходов автомата А, которым соответствуют прочеркнутые места в его таблице выходов. [9]
Эти соотношения означают, что таблица переходов эквивалентного автомата Мили совпадает с таблицей переходов автомата Мура, а таблица выходов составляется так, что в каждую ее клетку записывается сигнал, которым отмечено состояние в данной клетке. При этом граф автомата Мили отличается только тем, что выходные сигналы из узлов графа перенесены на все ветви, входящие в данный узел. [10]
Начальное состояние является неопределенным в случае, когда оно не встречается среди элементов таблицы переходов автомата. [11]
Полнота системы переходов в автомате означает, очевидно, что в каждом столбце таблицы переходов автомата должны встречаться символы всех его состояний. С учетом этого обстоятельства мы получаем следующие возможные типы запоминающих элементов. [12]
Эквивалентное преобразование автоматов Мура, устанавливаемое предложением 1.7, сводится к тому, что в таблице переходов автомата Мура символы запрещенных состояний заменяются черточками. [13]
Заметим, что неопределенность начального состояния в случае, когда оно не входит в число элементов таблицы переходов автомата, имеет место при любой области запрета. [14]
При задании ( частичного) автомата А таблицами переводов и выходов таблица переходов автомата В получается прочеркиванием всех мест таблицы переходов автомата А, которым соответствуют прочеркнутые места в его таблице выходов. [15]
Страницы: 1 2 3