Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Май 11, 2021  •  Реферат  •  416 Слов (2 Страниц)  •  284 Просмотры

Страница 1 из 2

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

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

Варіант №21

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

Завдання № 1

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

[pic 1]

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

21) 

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

E(E) , EE+E , EE*E , EV та VC[pic 3]

Vx та Vy

C1 та C2

Завдання № 2

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

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

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

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

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

21) 

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

S0A00B001B0011B

S1B11B111B

Отже з S0A ми отримуємо {00B, 001B, 00011B…}

S1B отримуємо {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.

...

Скачать:   txt (4.8 Kb)   pdf (384.3 Kb)   docx (1.4 Mb)  
Продолжить читать еще 1 страницу »
Доступно только на Essays.club