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

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

Листки семинаров

• Листок 1    
• Листок 2    
• Листок 3    
• Листок 4    
• Листок 5     

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

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

Также задачи и упражнения для самостоятельного решения приведены в семинарских листках. Дополнительные задачи, которые я упоминал на семинарах, собраны в листок . 

О строгости обоснований решений

Обращаем внимание, что в нашем курсе приняты следующие соглашения об обоснованиях. Любые решения без обоснования не оцениваются; любые объекты, построенные методом внимательного вглядывания оцениваются в 0 баллов (за соответсвующую часть задачи). Все построения и шаги решения должны быть обоснованы! Использование стандартного алгоритма из курса является обоснованием, однако при использовании алгоритма стоит привести проверяемый протокол. Примеры протоколов возникают при разборе задач на семинарах.

Ответы в духе «Да, по определению» не являются обоснованными, поскольку ничем не отличается от ответов «Нет, по определению», даже если далее приведены верные формулировки определений (но отсуствуют дальнейшие пояснения о том, почему объект из условия им удовлетворяет). В качестве примера обоснований, предлагаем ознакомиться с авторскими решениями (,) контрольных близкого курса. Также доступен файл с избранными решениями семинарских задач — он будет обновляться по мере продолжения курса. 

Программа семинаров

---

Наиболее полно программу семинаров отражают листки семинаров.

1. Регулярные выражения и конечные автоматы. Алгоримы:
   1. ДКА по РВ
   2. НКА по РВ
   3. ДКА по НКА
   4. минимизация ДКА
   5. конструкция произведения
   6. дополнение
   7. обращение
   8. НКА по ПГ
   9. ПГ по ДКА
2. Лемма о накачке
3. КС-грамматики и МП-автоматы. Алгоритмы:
   1. Приведение КС-грамматик (удаление недостижимых и бесплодных символов)
   2. Построение МП-автомата по КС-грамматике
4. LL-анализ. Алгоритмы:
   1. вычисление FIRST/FOLLOW
   2. построение LL(1)-анализатора
   3. удаление левой рекурсии
   4. факторизация
5. LR-анализ. Алгоритмы:
   1. построение LR(1)-анализатора
   2. построение LR(0)-анализатора
   3. преобразование LR(1)-анализатора к LR(0)-анализатору для LR(0)-грамматик

LR-анализ

---

Выкладываю презентацию с семинара. При построении таблицы анализатора и графа автомата Кнута я пользовался пакетом Parsing Table Generator for Compiler Theory, руководство к пакету по ссылке. Можете его попробовать.  

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

 

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

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

---

Общая контрольная состоится 22 мая. Последний семинар состоится 15 мая и будет посвящён оставшейся теме — LR-анализу.

Для подготовки к экзамену доступны следующие варинаты: 1, 2 (задача на атрибутные грамматики в программу не входит).

Задача о приёме слова НКА

---

На семинаре я дал всё же неправильное условие — линейного по входу алгоритма не получится. На вход задачи подаются описание НКА $\cal A$ и слово $w$. Необходимо привести полиномиальный (от длины описаний автомата и слова) алгоритм, проверяющий, что слово $ w $ принадлежит языку  $L(\cal A)$. У кого полином будет меньше, тот получит шоколадку.