Контрольні запитання на мкр №1

Мови програмування та мовні процесори

1. Які три аспекти як правило виділяють при вивчення мов програмування?

2. Які два поділи мов програмування в залежності від орієнтації на розв’язання тих чи інших класів задач вам відомі?

3. Які традиційні функції обробки типу даних “рядок” вам відомі?

4. Які два класи задач пов’язаних з синтаксичними структурами програм вам відомі?

5. Які два типи мовних процесорів вам відомі?

6. Опишіть структуру транслятора.

7. Що таке лексема?

8. Які два поділи оптимізації ви знаєте?

Лексичний аналіз та скінченні автомати

1. У чому призначення лексичного аналізу?

2. Що таке недетермінований скінчений автомат?

3. Яку мову розпізнає скінченний автомат?

4. Які два способи визначення функції переходів ви знаєте?

5. Спробуйте “зламати” вищенаведений автомат для цілочислових констант мови C (зверніть увагу на зауваження).

6. Що таке детермінований скінчений автомат?

7. Сформулюйте і доведіть теорему про детермінізацію скінченного автомата.

8. Нехай функція переходів $\delta$ не однозначна, але у той же час набуває не багато різних значень на одному наборі аргументів, наприклад не більше двох, тобто $\vert M(q, a)\vert \le 2$ для довільних $q \in Q$ і $a \in \Sigma$. Чи можна тоді отримати кращу оцінку зверху на кількість станів еквівалентного детермінованого автомату ніж $2^n - 1$?

Мінімізація детермінованих скінчених автоматів

1. Які автомати називаються еквівалентними?

2. Який стан автомату називається недосяжним?

3. Опишіть алгоритм пошуку недосяжних станів і доведіть його збіжність. Бонус: оцініть складність цього алгоритму за часом і пам’яттю.

4. Який стан автомату називається тупиковим?

5. Опишіть алгоритм пошуку тупикових станів і доведіть його збіжність. Бонус: оцініть складність цього алгоритму за часом і пам’яттю.

6. Які стани називаються еквівалентними?

7. Опишіть алгоритм пошуку еквівалентних станів і доведіть його збіжність. Бонус: оцініть складність цього алгоритму за часом і пам’яттю.

8. Опишіть алгоритм мінімізації детермінованого скінченного автомату. Бонус: виведіть з попередніх оцінок складність цього алгоритму за часом і пам’яттю.

Скінченно-автоматні мови і праволінійні граматики

1. Які три базові скінченно-автоматні мови ви знаєте?

2. Доведіть, що мови з попереднього питання справді є скінченно-автоматними.

3. Які три операції над скінченно-автоматними мовами ви знаєте?

4. Доведіть, що результати операцій з попереднього питання справді є скінченно-автоматними.

5. Що таке породжуюча граматика?

6. Які чотири типи граматик за Хомським ви знаєте?

7. Що таке праволінійна граматика?

8. Дайте визначення безпосереднього виведення, виведення, породженої граматикою мови.

9. Доведіть, що скінченний автомат це майже праволінійна граматика.

Регулярні множини і регулярні вирази

1. Яка множина називається регулярною (в алфавіті $\Sigma$)?

2. Як регулярні вирази позначаються регулярні множини?

3. Які класичні тотожності алгебри регулярних виразів ви знаєте?

4. Які не класичні тотожності алгебри регулярних виразів ви знаєте?

5. Який розв’язок лінійного рівняння $X = a \cdot X + b$ називається найменшою нерухомою точкою?

6. Доведіть, що згаданий у попередньому рівняння вираз справді є розв’язком.

7. Сформулюйте алгоритм Гауса розв’язування систем лінійних регулярних рівнянь.

8. Розв’яжіть систему $3\times3$:

   $$\left\{ \begin{aligned} X_1 &= a X_1 + b X_2 + c, \\ X_2 &= c X_1 + a X_2 + b X_3, \\ X_3 &= b + c X_2 + a X_3. \end{aligned} \right.$$

ПОЛІЗ, регулярні вирази, і автомати

1. Що таке ПОЛІЗ?

2. Чи можна в ПОЛІЗ опускати операції які природнім чином опускаються у класичному записі?

3. Яка основна характеристика ПОЛІЗ і яку обчислювальну перевагу вона пропонує?

4. Сформулюйте алгоритм перетворення регулярного виразу у ПОЛІЗ та оцініть його складність.

5. Що є результатом інтерпретації ПОЛІЗ регулярного виразу?

6. Сформулюйте алгоритм інтерпретації ПОЛІЗ регулярного виразу.

7. Оцініть складність попереднього алгоритму через складності операцій побудови автоматів.

8. Для регулярного виразу $(a^\star + b)^\star \cdot c$ побудуйте скінчений автомат, який розпізнає множину ланцюжків, що позначаються цим виразом.

(традиційні відповіді можна переглянути у коментарях у вихідному коді цієї сторінки)

Назад на головну