Мови, Граматики, Автомати
Автор: Heaven Punishment • Май 11, 2021 • Реферат • 416 Слов (2 Страниц) • 285 Просмотры
Тема: Мови, Граматики, Автомати.
Мета: Вивчити формальні породжувальні граматики, типи граматик, дерева виведення, форми Бекуса-Наура, скінченні автомати з виходом та без виходу, методи подання мов.
Варіант №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]
Стан | f | |
0 | 1 | |
[pic 6] | [pic 7] | [pic 8] |
[pic 9] | [pic 10] | - |
[pic 11] | - | [pic 12] |
[pic 13] | - | [pic 14] |
[pic 15] | [pic 16] | - |
[pic 17] | - | [pic 18] |
Завдання № 3
Побудувати граматику, яка породжує мову.
Хід виконання завдання:[pic 19]
21)
Порядок виконання дій:
Для початку напишемо декілька слів, щоб побачити закономірність:
1bb2, 11bbb22, 111bbbb222, бачимо, що завжди починається з 1, а закінчується 2.
...