Скінчені автомати та праволінійні граматики

Означення: Породжуюча граматика G – це п’ятірка

G=<N, S, P, S>,

де: N – скінчена множина - допоміжний алфавіт (нетермінали);

S – скінчена множина – основний алфавіт (термінали);

P – скінчена множина правил виду

a ® b, a Î (NÈS)* _* N _* (NÈS)*, b Î (NÈS).

S – виділений нетермінал (аксіома).

В залежності від структури правил граматики діляться на чотири типи (класифікація граматик по Хомському):

- Тип 0: граматики загального виду, коли правила не мають обмежень, тобто

a ® b, a Î (NÈS)* _* N _* (NÈS)*, b Î (NÈS).

- Тип 1: граматики, що не укорочуються, коли обмеження на правила мінімальні, а саме:

a ® b, a Î (NÈS)* _* N _* (NÈS)*, b Î (NÈS)*, |a| <= |b|.

- Тип 2: контекстно-вільні граматики, коли правила в схемі P мають вигляд:

A_i ® b, A_i Î N, b Î (NÈS)*.

- Тип 3: скінченоавтоматні граматики, коли правила в схемі P мають вигляд:

A_i ® wA_j, A_i, A_j Î N, w Î S*;

A_i ® w, w Î S*;

A_i ® wA_j, A_i, A_j Î N, w Î S*.

В класі скінченоавтоматних граматик виділимо так звані праволінійні граматики – це граматики, які в схемі Р мають правила виду:

A_i ® wA_j, A_i, A_j Î N, w Î S*;

A_i ® w, w Î S*;

Нескладно довести, що клас праволінійних граматик співпадає з класом граматик типу 3.

Означення: 1. Ланцюжок w₁ безпосередньо виводиться з ланцюжка w (позначається w Þ w₁), якщо w = xay, w₁ = xby та в схемі Р граматики G є правило виду a ® b. Оскільки поняття “безпосередньо виводиться” розглядається на парах ланцюжків, то в подальшому символ Þ в подальшому буде трактуватися як бінарне відношення.

2. Ланцюжок w₁ виводиться з ланцюжка w (позначається w Þ* w₁), якщо існує скінчена послідовність виду w Þ w¹, W¹ Þ w², … W^n-1 Þ w₁. Або кажуть, що бінарне відношення Þ* - це рефлексивно-транзитивне замикання бінарного відношення Þ.

3. Мова, яку породжує граматика G (позначається L(G)) – це множина термінальних ланцюжків:

L(G) = { w | S Þ* w, w Î S*}.

 

Твердження: Клас мов, що породжуються праволінійними граматиками, співпадає з класом мов, які розпізнаються скінченими автоматами.

Доведення. Спочатку покажемо, що для довільної праволінійної граматики G можна побудувати скінчений автомат М, такий що L(M) = L(G).

Розглянемо правила праволінійної граматики. Вони бувають двох типів:

- A_i ® wA_j, A_i, A_j Î N, w Î S*; (1)

- A_i ® w, w Î S*; (2)

На основі правил граматики G побудуємо схему P1 нової граматики, яка буде еквівалентною початковій, а саме:

- правила виду A_i ® а₁а₂…а_pA_j замінимо послідовністю правил:

A_i ® а₁B₁

B₁ ® а₂B₂

_{…………………}

B_p-1 ® а_pA_j ;

- правила виду A_i ® а₁а₂…а_p замінимо послідовністю правил:

A_i ® а₁B₁

B₁ ® а₂B₂

_{…………………}

B_p-1 ® а_p B _p

B_p ® e

де: B₁, B₂, … - це нові нетермінали граматики G₁. Очевидно, що граматика G₁ буде еквівалентна граматиці G.

Далі, на основі граматики G1 побудуємо скінчений автомат М, таким чином:

- як імена станів автомата візьмемо нетермінали граматики G1;

- початковий стан автомата позначається аксіомою S;

- функція d визначається діаграмою переходів, яка будується на основі правил виду A_i ® а_kA_j:

a_k

q_i q_j

- множина F заключних станів скінченого автомата визначається так:

F = {A_i | A_i ® e }.

Індукцією по довжині вхідного слова покажемо, що якщо S Þⁿ⁺¹ w, то (q₀, w) |=ⁿ (q, e):

Базис i = 0: S Þ e, тоді (q₀, e) |=⁰ (q₀, e).

Нехай |w| = i+1, тобто w = aw₁ : тоді S Þ aA_p Þⁱ aw₁ та

(q₀,aw₁) |= (q_i,w₁) |=^i-1 (q, e), q Î F.

Доведення навпаки є очевидним.