АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. C) Умения, доведения до автоматизма, высокой степени совершенства
  2. GIP-M. АВТОМАТИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ ДОРОГ
  3. III Механизация, Электрификация и автоматизация сельскохозяйственного производства
  4. А. Автоматическая блокировка – однопутный участок.
  5. Автоматизация деятельности по криминалистической регистрации.
  6. Автоматизация документооборота
  7. Автоматизация документооборота компании
  8. Автоматизация звука
  9. Автоматизация звука в слогах и словах.
  10. АВТОМАТИЗАЦИЯ ЗВУКА ЗЬ
  11. Автоматизация производственных процессов - Этапы развития автоматизации производственных процессов
  12. Автоматизація виробництва

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

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.

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)