Автоматная (регулярная) грамматика и конечный автомат

Автоматная грамматика AG =〈A, V, P, S₀〉, где A – основной алфавит; P – правила вида v_i→a_jv_j,,v_i,v_j∈ V, a_j∈ A, s₀ – аксиома.

Конечный автомат AK =〈A,S,P,s₀,s_k〉, где A – основной алфавит; S – алфавит состояний; s₀ – начальное состояние; s_k– конечное состояние; P – правила вида s_i,a_i→s_j,s_i,s_j∈ S, a_j∈A.

Пример. Для языка L1 заданы:

1. •AG = 〈A,V,P,S₀〉

• A = {a, b, c}∪{ Δ }

• V = {S₀, S₁}

2. • KA = 〈A, V, P, S₀, S_k〉

•A = {a, b, c}∪ { Δ }

• V = {S₀, S₁, S_k}

Δ – маркер конца слова.

AG – правила порождения:

1. S₀ →aS₀

2. S₀ →cS₁

3. S₁→bS₁

4. S₁ → Δ

KA – правила перехода:

1. S₀,a→S₀

2. S₀,c → S₁

3. S₁,b → S₁

4. S₁, Δ →S_k

AG порождает слова языка L₁. KA распознаёт слова языка L 1. Если заданы правила AG, то правила KA получаются формальными переносами символов A из правой части правил в левую (см. пример). Если заданы правила KA, то правила AG переносом символов A в правую часть правил.

KA задается графом переходов и, по сути, является машиной состояний (SM). См. рис. 6.

Рис. 6. Граф переходов

Рис. 7. Граф переходов 1

Кроме того, автоматный язык задается регулярным выражением (формулой из букв A, знаков операций: • –конкатенация, _* – итерация, ∨ – разделённое «или»). Для примера выше регулярное выражение для L₁ = ((a)* · c(b)* Δ).

Пример. Пусть для языка L₂ на рисунке задан граф KA и слово w₁ = a · a · c · b· c Δ, говорят, что w₁ распознаётся KA, если находясь в S₀ под действием w₁ попадает в S_k. Слово w₂ = a · c · b· b· a Δ не распознаётся KA; KA из S₀ под действием w₂ останется в S₁, т. к. нет правила выводящего из S₁ под действием какого-либо символа кроме b и Δ. См. рис. 7.