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

Означення: Породжуюча граматика 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 мають вигляд:

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

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

Ai ® wAj, Ai, Aj Î N, w Î S*;

Ai ® w, w Î S*;

Ai ® wAj, Ai, Aj Î N, w Î S*.

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

Ai ® wAj, Ai, Aj Î N, w Î S*;

Ai ® w, w Î S*;

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

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

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

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

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

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

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

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

- Ai ® wAj, Ai, Aj Î N, w Î S*; (1)

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

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

- правила виду Ai ® а1а2…аpAj замінимо послідовністю правил:

Ai ® а1B1

B1 ® а2B2

…………………

Bp-1 ® аpAj ;

- правила виду Ai ® а1а2…аp замінимо послідовністю правил:

Ai ® а1B1

B1 ® а2B2

…………………

Bp-1 ® аp B p

Bp ® e

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

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

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

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

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

ak

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

qi qj

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

F = {Ai | Ai ® e }.

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

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

Нехай |w| = i+1, тобто w = aw1 : тоді S Þ aAp Þi aw1 та

(q0,aw1) |= (qi,w1) |=i-1 (q, e), q Î F.

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

Наши рекомендации