Мови, Граматики, Автомати

Тема: Мови, Граматики, Автомати.

Мета: Вивчити формальні породжувальні граматики, типи граматик, дерева виведення, форми Бекуса-Наура, скінченні автомати з виходом та без виходу, методи подання мов.

Варіант №21

Порядок виконання завдання: Скласти комп’ютерні програми із зазначеними вхідними даними та результатами для завдань 1-3.

Завдання № 1

Задано множину продукцій у формі Бекуса-Наура:

[pic 1]

Хід виконання завдання:[pic 2]

21) 

Порядок виконання дій:

E→(E) , E→E+E , E→E*E , E→V та V→C[pic 3]

V→x та V→y

C→1 та C→2

Завдання № 2

Дано граматику G=(V, T, S, P), де V={0, 1, S, A, B}, T={0,1}, S – початковий символ. Виконати наступні завдання:

-Побудувати мову, породжену такою граматикою.

-Визначити тип граматики;

-Побудувати недетермінований скінчений автомат, що допускає мову, породжену даною граматикою; задати автомат діаграмою та таблицею.

Хід виконання завдання:[pic 4]

21) 

Порядок виконання дій:

S→0A→00B→001B→0011B

S→1B→11B→111B

Отже з S→0A ми отримуємо {00B, 001B, 00011B…}

S→1B отримуємо {1B, 11B, 111B…}

Спроба побудови виведення результату в цій граматиці приводить нас до ланцюжка, який виявляється нескінченним. Тобто граматика породжує порожню мову. Граматика буде типу 1, бо вона є контексно вільною.

[pic 5]

Завдання № 3

Побудувати граматику, яка породжує мову.

Хід виконання завдання:[pic 19]

21) 

Порядок виконання дій:

Для початку напишемо декілька слів, щоб побачити закономірність:

1bb2, 11bbb22, 111bbbb222, бачимо, що завжди починається з 1, а закінчується 2.