Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 36 стр.

UptoLike

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

γ - функция выходов, задающая отображение КХУ.
Функционирование автомата можно задать множеством команд вида qx py, где q и p
K, x X, y Y.
Пусть на некотором такте t
i
управляющее устройство находится в состоянии q, а из
входной ленты читается символ x. Если в множестве команд есть команда qx py, то на
такте t
i
на выходную ленту записывается символ y, а к следующему такту t
i+1
управляющее
устройство перейдет в состояние p, т.е.:
y(t) = γ(q(t), x(t)), q(t+1) =δ(q(t), x(t)).
Если же команда qx py отсутствует, то автомат оказывается блокированным и не
реагирует на символ, принятый в момент t
i
, а также перестает воспринимать символы в
последующие моменты времени.
В соответствии с определением неинициального автомата в начальный момент
состояние автомата может быть произвольным.
Если зафиксировано некоторое начальное состояние, то такой автомат называют
инициальным, т.е. q(0) = q
0
.
Инициальный автомат - это шестерка вида А = (К, X, Y, δ, γ, q
0
), где
К - множество состояний (алфавит состояний);
Х - входной алфавит;
Y - выходной алфавит;
δ - функция переходов (отображение К Х К);
γ - функция выходов (отображение К Х У);
q
0
- начальное состояние.
5.3. Распознаватели
5.3.1. Языки и автоматы
Задача грамматического разбора заключается в нахождении вывода цепочки в заданной
грамматике и определения дерева вывода этой цепочки.
Языки могут быть заданы двумя способами:
1) грамматиками (порождающее средство языка);
2) автоматами (распознающее средство языка).
Различным по сложности автоматам соответствуют разные типы языков. Простейшим
типом автоматов являются конечные автоматы.
Конечный автомат имеет входную ленту, с которой за один такт может быть считан один
входной символ. Возврат по входной ленте не допускается.
Конечным автоматом называется пятерка вида А = (К, , δ, p
0
, F), где
К - конечное множество состояний;
- алфавит;
δ - функция переходов;
p
0
- начальное состояние;
F - множество заключительных состояний.
Автомат можно определить как формальную систему через состояния, через символы,
которые пишутся (читаются) с ленты или с нескольких лент, и через набор команд.
Конечный автомат можно представить графом, таблицей переходов, командами, а также
матрицей переходов.
5.3.2 Регулярные множества
Регулярные множества образуют класс языков, имеющих важное значение для теории
формальных языков. Рассмотрим несколько методов задания языков, каждый из которых