Теория алгоритмов и формальных языков. Мелихов А.Н - 63 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

который начинается из вершины, помеченной аксиомой А
1
и заканчивается в
концевой вершине k. Графы грамматик G
n
и G
A
показаны соответственно на
рис. 3.6,а,б.
Рис. 3.6
Подчеркнем особо, что граф КС-грамматики в общем случае задается в
виде бесконечного графа.
3.5. Конечные автоматы и способы их задания
Конечные автоматы (КА) - подкласс машин Тьюринга, которые
распознают А-языки. Условно КА можно представить в виде входной ленты,
ограниченной
слева и неограниченной справа, и устройства управления (УУ)
с головкой, читающей символы на входной ленте так, как показано на рис.
3.7.
КА имеет конечный входной алфавит
{}
nT
xxxV ,...,,
21
= ,
конечное множество состояний
{}
k
qqqQ ,...,,
10
=
, где
0
q -
начальное состояние. Функционирование КА можно
описать следующим образом. На ленту записывается
входное слово
n
T
Vd ∈ . Считается, что справа от d
записаны пробелы
ε
, автомат находится в состоянии
0
q ,
а головка обозревает самый левый символ
1
x слова d. То
есть КА находится в начальной ситуации
()
i
xq ,
0
.
Рис.3.7 Прочтя
i
x , КА переходит в новое состояние Qq
j
∈ ,
сдвигает ленту на одну ячейку влево и тем самым оказывается в новой ситуации и так
далее. Таком образом, команды КА имеет вид
(
)
ij
xq ,
k
q→ . Число команд КА конечно.
Если после выполнения начислений над входом словом d КА возвращается к ситуации
()
ε
,
0
q , то говорят , что автомат допускает слово d КА возвращается к ситуации
()
ε
,
0
q , то
говорят, что автомат допускает слово d. Множество слов, допустимых автоматом, есть по
определению язык, допустимый этим автоматом. Покажем, что класс языков,
допускаемых конечными автоматами, совпадает с классом А-языков.
х
1
А
1
х
1
А
2
х
2
х
2
k
а)
х
2
А
1
х
2
А
2
х
1
х
1
k
б)
Входная лента
YY
1i
x
3i
x
2i
x
in
x
K

Страницы