Конечные автоматы
Определение языка конечными средствами возможно не только при помощи формальных грамматик, но также путем использования математической модели устройства, распознающего предложения языка.
Конечный автомат – это простейший распознаватель (см. п.2) без вспомогательной памяти.
Конечный автомат действует следующим образом:
§ В начале он находится в состоянии S
§ На вход КА поступают символы входной ленты, принадлежащие входному алфавиту
§ Находясь в некотором состоянии и получив на вход очередной символ, автомат переходит в следующее состояние, определяемое значением функции переходов для данной пары символ-состояние, и считывает очередной символ.
Конечным автоматом (КА) называется пятерка:
К=(Q, S, d, q0, F)
Где
Q – конечное множество состояний автомата
S– входной алфавит – конечное множество символов
d –функция переходов автомата (в общем случае неоднозначная): отображение множества Q ´Sв множество P(Q), т.е. d: (Q ´S) ® P(Q) , где P(N) – множество всех подмножеств множества N
q0 –начальное состояние. g0 Î Q;
F –множество конечных (финишных) состояний FÍQ (F включается в Q)
Формально конфигурацией автомата называется пара (q, v) Î Q ´S*, конфигурация (q0, v) называется начальной, а (q , e), где q Î F – заключительной.
Такт работы КА представляется бинарным отношением (├), определенным на множестве конфигураций. Если q’ Î d(q, a), то (q, aw) ├ (q’, w) для всех w Î S*.
Говорят, что конечный автомат К=(Q, S, d, q0, F) допускает (распознает) входную цепочку w Î S, если (q0, w) ├ (q, e) для некоторого q Î F.
Языком, определяемым (допускаемым, распознаваемым) КА, называется множество всех входных цепочек, допускаемых этим автоматом, т.е.
L(K) = {w | w Î S и (q0, w) ├ *(q, e) для некоторого q Î F }
Пример 1.Рассмотрим КА К = ({q0, q1, q2, q3,}, {a, b}, d, q0, { q3} ), в котором функция переходов выглядит следующим образом:
| 1) d(q0, a) = {q1} | 2) d(q0, a) = {q0} |
| 3) d(q1, a) = {q1} | 4) d(q1, b) = {q2} |
| 5) d(q2, a) = {q3} | 6) d(q2, b) = {q0} |
| 7) d(q3, a) = {q3} | 8) d(q3, b) = {q3} |
Для входной цепочки baababa автомат выполнит следующую последовательность действий:
(q0, baababa) ├ (q0, aababa) ├ (q1, ababa) ├ (q1, baba) ├ (q2, aba) ├ (q3, ba) ├ (q3, a) ├ (q3, e)
Таким образом, цепочка baababa принадлежит языку L(K)