Синтез цифровых автоматов. Захаров Н.Г - 45 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

44
стояний, отмеченных пустым множеством ( ), или выходной сигнал ( ) представляет
событие, состоящее из всех слов входного алфавита, не вошедших в заданные события.
В процессе синтеза автомата или по окончании этого процесса производят пе-
реобозначения состояний и выходных сигналов с целью упрощения записи таблиц
переходов и выходов. Обычно при переобозначении состояний их просто нумеруют
натуральными числами 1, 2, ..., используя для обозначения начального состояния
единицу. В некоторых случаях оказывается целесообразным обозначать состояния
числами 0, 1, 2, ..., тогда начальное состояние обозначается всегда нулем.
Рассмотрим пример синтеза конечного автомата в соответствии с описанным
алгоритмом.
Пусть требуется построить конечный автомат, в котором для входного алфави-
та Х, состоящего из двух букв х и у, были бы представлены два события: событие R
1
,
состоящее из всех слов в алфавите Х, в которых все буквы х предшествуют всем бук-
вам у, и событие R
2
, состоящее из всех слов в алфавите Х, которые кончаются
буквой х.
Применяя правило 1, записываем заданные события в виде следующих регу-
лярных выражений:
R
1
= {x}{y} , R
2
= {x ∨ y} x.
После разметки мест эти выражения приобретут вид:
R
1
′ = |{| x |}|{| y |}| , R
2
′ = |{| x | ∨ | y |}| x |.
Применяем правило 2, в результате получим выражения:
R
1
′′ = |{| x |}|{| y |}| , R
2
′′ = |{| x | ∨ | y |}| x |.
0 1 2 0 3 4 5
В результате применения правила 3 получаем:
R
1
′′′ = |{| x |}|{| y |}| , R
2
′′′ = |{| x | ∨ | y |}| x |.
0 1 2 0 3 4 5
0 0 0 0 0 0 0
1 1 1 1 3 3 3
2 2 4 4 4
Применение правила 4 приводит к построению таблицы переходов 3.1.
Применение правила 5 дает отмеченную таблицу переходов 3.2.
Обозначая выходные сигналы ( ), (R
1
), (R
2
), (R
1
, R
2
) соответственно через z, u, v
и w и, нумеруя состояния, переходим к отмеченной таблице переходов 3.3.
При интерпретации построенного автомата как автомата Мили в соответствии
с правилом 6 мы получим таблицу его выходов 3. 4.
Таблица 3.1
0
1 ∨ 3 ∨ 5 2 ∨ 4 3 ∨ 5
4
х
у
1 ∨ 3 ∨ 5
2 ∨ 4
1 ∨ 3 ∨ 5
2 ∨ 4
3 ∨ 5
2 ∨ 4
3 ∨ 5
4
3 ∨ 5
4

Страницы