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

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

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

Материалы для подготовки к экзамену

---

Выкладываю вариант для подготовки к экзамену.

---

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

 

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

 

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

Теорема Майхилла-Нероуда

---

С теоремой Майхилла-Нероуда, которая позволяет доказывать как регулярность, так и нерегулярность языка, можно ознакомиться в тексте Задания 5 к аналогичному курсу.

Домашние упражнения на 17/04

---

1. Найти ошибку в алгоритме минимизации конечного автомата.

2. Доказать или опровергнуть контрпримером, что грамматика $S \to SaSbS\mid SbSaS\mid \varepsilon $ порождает язык $\{w \mid |w|_a = |w|_b \}$.

3. Придумать грамматику для правильных скобочных выражений с двумя типами скобок (и доказать корректность) или разобраться с доказательством корректности известной грамматики.