Конечные автоматы

Определение языка конечными средствами возможно не только при помощи формальных грамматик, но также путем использования математической модели устройства, распознающего предложения языка.

Конечный автомат – это простейший распознаватель (см. п.2) без вспомогательной памяти.

Конечный автомат действует следующим образом:

§ В начале он находится в состоянии S

§ На вход КА поступают символы входной ленты, принадлежащие входному алфавиту

§ Находясь в некотором состоянии и получив на вход очередной символ, автомат переходит в следующее состояние, определяемое значением функции переходов для данной пары символ-состояние, и считывает очередной символ.

Конечным автоматом (КА) называется пятерка:

К=(Q, S, d, q₀, F)

Где

Q – конечное множество состояний автомата

S – входной алфавит – конечное множество символов

d – функция переходов автомата (в общем случае неоднозначная): отображение множества Q ´Sв множество P(Q), т.е. d: (Q ´S) ® P(Q), где P(N) – множество всех подмножеств множества N

q₀ – начальное состояние. g₀ Î Q;

F – множество конечных (финишных) состояний FÍQ (F включается в Q)

Формально конфигурацией автомата называется пара (q, v) Î Q ´S^*, конфигурация (q_0, v) называется начальной, а (q, e), где q Î F – заключительной.

Такт работы КА представляется бинарным отношением (├), определенным на множестве конфигураций. Если q^’ Î d(q, a), то (q, aw) ├ (q’, w) для всех w Î S^*.

Говорят, что конечный автомат К=(Q, S, d, q₀, F) допускает (распознает) входную цепочку w Î S, если (q₀, w) ├ (q, e) для некоторого q Î F.

Языком, определяемым (допускаемым, распознаваемым) КА, называется множество всех входных цепочек, допускаемых этим автоматом, т.е.

L(K) = {w | w Î S и (q₀, w) ├ *(q, e) для некоторого q Î F }

Пример 1. Рассмотрим КА К = ({q₀, q₁, q₂, q₃,}, {a, b}, d, q₀, { q₃}), в котором функция переходов выглядит следующим образом:

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 автомат выполнит следующую последовательность действий:

(q₀, baababa) ├ (q₀, aababa) ├ (q₁, ababa) ├ (q₁, baba) ├ (q₂, aba) ├ (q₃, ba) ├ (q₃, a) ├ (q₃, e)

Таким образом, цепочка baababa принадлежит языку L(K)

Дата добавления: 2014-01-03