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

UptoLike

ВУЗ: 

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

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

Рубрика: 

27
а язык, допускаемый автоматом А, это
L(A) = {α | δ(q
0
, α)∈ F}.
Рассмотрим пример детерминированного конечного автомата
А = (X, Q, δ, q
0
, F),
где Х = {a, b}; Q = {S, Y, Z, T}; q
0
= S; F = {T}, а δ задается диаграммой состояний,
представленной на рис. 2.3.
Рис. 2.3. Диаграмма состояний детерминированного конечного автомата
Очевидно, что язык, допускаемый этим автоматом,
L(A) = {M
n
| n ≥ 1},
где M = {aa, bb}.
Цепочка α
1
= aabbaa, допускается данным автоматом, так как после ее про-
смотра автомат окажется в состоянии Т∈ F.
Цепочка aabba не допускается, так как после ее просмотра автомат окажется в
состоянии Y, не являющемся заключительным.
Цепочка abb не допускается потому, что после считывания символа а автомат
окажется в ситуации (Y, b), для которой нет команды.
Недетерминированный конечный автомат – есть пятерка того же вида.
Единственное отличие заключается в том, что значениями функции переходов явля-
ются не состояния, а множество состояний (или, в терминах команд, возможны раз-
личные команды с одинаковыми левыми частями. Это соответствует тому факту, что
в диаграмме состояний из одной вершины может исходить несколько дуг с одинако-
вой пометкой.
2.2. Машины Тьюринга с двумя выходами
С точки зрения лингвистики машины Тьюринга можно рассматривать как рас-
познающие устройства, допускающие языки самого широкого из рассмотренных
классов: языки типа 0 или рекурсивно-перечислимые множества.
Машина Тьюринга состоит из конечного управляющего устройства, входной
ленты и головки, которая в отличие от головки конечного автомата может не только
считывать символы с ленты, но и записывать на нее новые символы. Лента считается
бесконечной. Перед началом работы n ячеек ленты содержат символы входной це-
почки
n21
iiii
x,...,x,x=α , все остальные ячейки считаются заполненными специаль-
ным символом В («пустое место»), который не является входным (рис. 2.4).
Формально машина Тьюринга определяется как следующая шестёрка:
Т = (V
1
, V
2
, Q, δ, q
0
, F),
где V
1
= {a
1
, ..., a
n
} – входной алфавит (конечное множество символов);
S
Y Z
T
a
a
a
b
b
b

Страницы