Реферат на тему: «КОНТЕКСТНО-ВІЛЬНІ ГРАМАТИКИ»

Зміст

1. Контекстно-вільні граматики (КВ-граматики)    3

2. Застосування контекстно-вільних граматик    10

3. Неоднозначність в граматиках і мовах    21

1. Контекстно-вільні граматики (КВ-граматики).

За визначенням КВ-граматики можуть бути, як скорочувані, так і не скорочувані. У КВ-граматик, що скорочуються, множина продукцій містить продукції виду . Очевидно, що ніяка інша продукція не може привести до зменшення довжини рядка при виводі.

Наявність у КВ-граматики продукцій виду ускладнює процедуру граматичного розбору і висновків в КВ-граматиці.

Продукцію виду називатимемо е-продукціею, а граматику, яка не має такої продукції е-вільною.

Теорема 1. Про -вільну граматику.

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

Очевидно, що КВ-граматики не містить продукцій виду

Доведення

А. Нехай в продукціях КВ-граматики є продукції виду , де .

В. Проведемо ефективну процедуру еквівалентного перетворення КВ-граматики в еквівалентну їй КВ-граматику .

Крок 1. Представимо множину продукцій КВ-граматики як об’єднання непересічних множин і , таких що містить все е-продукції із множини продукцій .

.

Крок 2. Фіксуємо деяку продукцію з множини .

Крок 3. Додаємо в множину продукції з множини продукцій в яких опущені -породжуючі не термінальні знаки .

Крок 4. Видаляємо з множини вибрану продукцію і переносимо з множини в множину нові -продукції, які з’явилися в множині на кроці 3.

Крок 5. Якщо всі -продукції з множини переглянуті, тобто , то завершуємо ефективну процедуру. Інакше переходимо до кроку 2.

С. Будуємо граматику таким чином:

  1. Множини , які містять ті термінальні і не термінальні знаки, що присутні в продукціях множини .
  2. Аксіома
  3. Множина продукцій містить продукції множини отриманого в пункті В.

Ми задали всі чотири елементи КВ-граматики отже ми повністю визначили граматику .

D. Приведена в пункті В
ефективна процедура результативна, тобто завершується
за скінчене число кроків оскільки потужність множини продукцій скінчена. Може вийти, що множина і на кожному кроці 3
з’являтиметься нова така ж продукція в множині . Це може служити ще однією умовою завершення ефективної процедури.

Е. Для кожного висновку в КВ-граматиці існує висновок в КВ-граматиці результатом якої буде той же рядок. Вірно і зворотне.

.

F. Якщо множина складатиметься з продукції коли ми зупинили ефективну процедуру, видаливши цю продукцію з , то тим самим ми виключили з мови порожній рядок.

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

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Konteksno-vilni Gramatyky (1.2 MiB, Завантажень: 2)

Сторінка: 1 2 3 4 5 6 7 8 9 10 11
завантаження...
WordPress: 23.51MB | MySQL:26 | 0,365sec