Формальные языки и автоматы

Я буду размещать здесь задачи, рекомендованные для самостоятельного решения. Если вы хотите, чтобы я их проверил, приносите свои решения. Если вы хотите прорешать больше задач, то их можно найти в заданиях к аналогичному курсу. В каждом задании есть теоретическая часть, обращаю внимание, что в ней могут быть ошибки и неточности.

Задачи и упражнения для самостоятельного решения

• Задачи по регулярным языкам и конечным автоматам  
• Задание по КС-языкам и магазинным автоматам

Список допущенных до досрочного экзамена

---

324 группа

1. Константинова Татьяна Сергеевна
2. Спиридонова Марина Владимировна
3. Филин Максим Дмитриевич
4. Хзмалян Размик Эдвардович

325 группа

1. Александров Сергей Витальевич
2. Боднарюк В.В.
3. Гончарова А.Ю.
4. Дебнатх Д.
5. Зпангиров О.А.
6. Мартынов Роман
7. Постников М.М.
8. Пучкин Д.А.
9. Себко Е.С.
10. Терёшина М.С.
11. Тихонова Е.А.

Задачи на LR

---

Для подготовки к экзаменам в плане LR, я рекомендую прорешать задачи 36-41 отсюда. Также на конструкторе анализаторов я рекомендую разобраться со следующими грамматиками:

 

Пример 1.

Задачи на LR

---

Для подготовки к экзаменам в плане LR, я рекомендую прорешать задачи 36-41 отсюда. Также на конструкторе анализаторов я рекомендую разобраться со следующими грамматиками:

 

Пример 1.

 

Вариант для подготовки и семинар

---

Выкладываю вариант для подготовки к экзамену (задача на атрибутные грамматики в программу не входит). Для того, чтобы попасть на досрочный экзамен, к нему нужно допуститься, поэтому в начале семинара я дам короткий тест на понимание происходящего в курсе, по результатам которого и другим дополнительным факторам я буду решать кого допускать до досрока.

На семинаре я продолжу рассказ про LR, после чего, если успеем, разберём какие-нибудь задачи из варианта для подготовки.

Анализаторы

---

Мы подошли к практической части нашего курса, почти всё что было до построения анализаторов покрывалось книгой  Хопкрофта, Мотвани и Ульмана. Я рекомендую изучать алгоритмы построения анализаторов по книжке Серебрякова и по Dragon Book (Ахо, Сети, Ульман). В последней они описаны более подробно. Почему это всё работает, написано в книжке Ахо и Ульмана, но её очень сложно понять и расстояние между двумя нужными для понимания утверждениями порой достигает 100 страниц. Про LR-анализаторы также написано в книжке Шеня, там есть хороший шанс понять что происходит.

 

Для проверки и более наглядного изучения есть конструктор анализаторов.  По умолчанию все нетерминалы — заглавные буквы, все терминалы — строчные. Правила записываются в виде "A -> a|B". Каждое правило, быть может с разделителями, начинается с новой строки. Пустое слово = e.

 

Если запускать программу под IE, то можно, при некоторой удаче, увидеть дерево разбора анализируемого слова. Под остальными браузерами придётся включать воображение и соединять точки.

Упражнения ко второму семинару

---

Задача 1. Минимизируйте ДКА из задачи 3 из упражнений к первому семинару.

Полезная деятельность: изучите алгоритм КМП и его связь с автоматами и сравните полученный ДКА с КМП-автоматом.

Задача 2. Постройте Нка по РВ $(a^*(b|ba))^*(a|b)$. Детерминизируйте его и минимизируйте полученный ДКА.

Вообще, я рекомендую на экзаменах пользоваться алгоритмом построения ДКА по РВ — он получается быстрее и даёт меньше ошибок, чем связка РВ $\to$ НКА $\to$ ДКА.

Задача 3. Постройте ДКА, распознающий все слова чётной длины, в которых число букв $a$ даёт остаток $2$ по модулю $3$. То есть ДКА, распознающий язык $ L = \{ w \mid |w| = 2k, |w|_a = 2 \mod 3 \}$.

Указание: постройте два ДКА, удовлетворяющих каждому условию и постройте их пересечение.

Задача 4. Докажите, что язык палиндромов: слов, читающихся слева направо и справа на лево одинаково,— над алфавитом $\{a,b\}$ является нерегулярным.

Задача 5. Докажите, что язык $\{ b^p \mid p \text{ простое число} \}$ не является регулярным.

Задача 6. Докажите, что для языка $L = b^*\cup \{ ab^{p} \mid p \text{ простое число} \} \cup aa^{+}b^*$ удовлетворяет лемме о накачке. $a^{+} = aa^*$.

Задача 6*. Докажите, что язык из задачи 6 нерегулярен. 

Упражнения к первому семинару

---

Задача 1. Построить регулярное выражение и детерминированный конечный автомат для языка над алфавитом $\Sigma = \{a,b\}$, состоящего из слов, в которые буква $a$ входит чётное число раз. Формально $L = \{ w \mid |w|_a = 2k, k \geq 0 \}$. Доказать равенства языка $L$ с языками, порождаемыми соответствующими РВ и ДКА.

Обращаю внимание, что несмотря на последнюю фразу в этой задаче, в нашем курсе все построения всегда должны быть обоснованы. Применение алгоритма из курса является обоснованием.

 

Задача 2. Построить ДКА (используя алгоритм РВ $\to$ ДКА), распознающий язык, заданный регулярным выражением $(a|b)((a|bb)^*ab)^*$.

 

Задача 3. Постройте ДКА, распознающий язык $\Sigma^*aab\Sigma^*$, где $\Sigma = \{a,b\}$.

 

Больше задач можно найти на странице аналогичного курса. Можно решать задачи как из еженедельных заданий, так и из канонического задания.