Головна

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

  1. III. Движение поездов при неисправности полуавтоматической блокировки
  2. quot;B1", "C1", "D1" С АВТОМАТИЧЕСКОЙ ТРАНСМИССИЕЙ
  3. RFID (Radio Frequency IDentification) - автоматическая идентификация продукта при помощи радиочастотных меток.
  4. VI. Движение поездов при автоматической локомотивной сигнализации, применяемой как самостоятельное средство сигнализации и связи
  5. А) Системы автоматизации отдельных разделов бухгалтерского учета.
  6. АВС-36, автоматическая винтовка Симонова образца 1936 г.
  7. Автоматизация анализа финансового состояния предприятия

Означення: Породжуюча граматика 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 нової граматики, яка буде еквівалентною початковій, а саме:

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

Ai ® а1B1

B1 ® а2B2

...

Bp-1 ® аpAj ;

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

Ai ® а1B1

B1 ® а2B2

...

Bp-1 ® аp B p

Bp ® e

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

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

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

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

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

ak

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.

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

 



Мінімізація детермінованих скінчених автоматів | Регулярні множини та регулярні вирази

Мови програмування та мовні процесори | Структура транслятора | Скінчені автомати | Польський інверсний запис для регулярних виразів | Застосування скінчених автоматів при розробці лексичних аналізаторів | На основі поточного стану. | Методика програмування лексичних аналізаторів на основі скінчених автоматів. | Лабораторний практикум побудови лексичних аналізаторів. | Синтаксичний аналіз в мовних процесорах | Мал. 2. |

© um.co.ua - учбові матеріали та реферати