Приклад 3

Приклад 2.

Приклад 1.

Розглянемо граматику G=(V,T,S,P). Нехай S- початковий символ,. Ланцюжок AaBa виводиться з ABa, оскільки є продукцією граматики. Ланцюжок породжується ланцюжком, оскільки

за допомогою послідовного використання продукцій

Нехай G=(V,T,S,P)- граматика.

Означення:

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

Мовою, що порядкується граматикою G, позначають L(G).

Отже L(G)=, де –множина всіх ланцюжків терміналів,включно з порожнім ланцюжком.

Нехай G- граматика з алфавітом, множиною терміналів Т=,початковим символом S і множиною продукцій Р=. Знайдемо мову L(G), яка порядкується цією граматикою.

Розв'язання:

Із початкового символу S можна вивести ланцюжок А, використовуючи продукцію; або застосовуючи продукцію щоб вивести. З скориставшись продукцією, можна вивести ланцюжок. Ніяких інших ланцюжків вивести не можна. Отже L(G)=.

.

3. Виведення в мовах, породжених контекстно вільними граматиками, можна зображати графічно з використанням кореневих дерев.

У такому разі ці дерева називають деревами виведення, або деревами синтактичного розбору.

Кореню дерева виведення відповідає початковий символ,внутрішнім вершинам – не термінальні символи, що зустрічаються у виведення, листками –термінальні символи. Нехай ланцюжок і продукція,використана у виведенні. Тоді вершина, яка відповідає не термінальному символу А, має синами вершини, які відповідають кожному

символу ланцюжка у порядку зліва направо

C

C

A

S

b

a

B

b

(мал.1)

Визначимо, чи належить ланцюжок мові, породженій граматикою G=(V,T,S,P), де S-початковий символ, а множина продукцій

Розв’язати цю задачу можна двома способами:

1.Розбір зверху вниз.

Оскільки є лише одна продукція з початковим символом S у лівій частині, то виведення починаємо з. Далі використаємо продукцію. Отже, маємо.

Оскільки починається з символів, то використовується продукцію, це дасть.

Завершуємо виведення використанням продукції:

Отже, ланцюжок належить мові L(G).

2. Розбір знизу верх.

Починаємо з ланцюжка,який потрібно вивести:.Можна використати продукцію,отже,.

Далі застосуємо продукцію, тоді матимемо.

З використанням продукції, отримаємо. Нарешті використаємо продукцію.

Дерево виведення для рядка у граматиці G зображено (мал.1).

Нормальні алгоритми Маркова є ще однією формалізацією інтуїтивного поняття алгоритму. Теорія нормальних алгоритмів була створена наприкінці 40-х-початку 50-х років ХХ століття російським математиком Андрієм Марковим (1903-1979), який назвав їх нормальними алгоритмами.

Підстановки Маркова

Підстановка Маркова – це операція над словами в даному алфавіті

V (пусте слово позначається, але операція задається за допомогою впорядкованої пари слів (Р, Q) і полягає в тому, що в заданому слові R знаходять перші входження слова Р, і не змінюючи інших частин слова R, замінюють це входження словом Q. Отримане слово називається результатом застосування підстановки Маркова (Р, Q) до слова R.

Якщо ж першого входження слова Р в мові R немає, то вважається, що підстановка Маркова (Р, Q) не застосовується до слова R. Підстановку Маркова, що задається за допомогою пари слів (Р, Q), позначають Р.

У зв’язку з можливістю розгляду пустих слів виникає питання, що означає підстановка Маркова тобто, що означає в дане слово w підставити слово v замість першого входження в w пустого слова Згідно означення, випливає, що результатом даної підстановки є слово v w

Дата добавления: 2014-01-07