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

Лектор — Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)

Практика — Михаил Эдуардович Дворкин

День зачёта

10:00—11:30 Тест. Письменный, решение задач на темы курса. В этой части пользоваться книгами и конспектами нельзя. Проверяться будет понимание, а не выучивание.

12:30 Объявление результатов теста. Варианты могут быть: получение зачёта, вытягивание 1 теорвопроса, вытягивание 2 теорвопросов.

12:30—... Подготовка теорвопросов, сдача их в порядке живой очереди. Можно пользоваться конспектом, книгами, интернетом.

Список теорвопросов

• Детерминированные конечные автоматы. Эквивалентность состояний. Минимизация ДКА.
• Недетерминированные конечные автоматы с eps-переходами. Детерминизация НКА.
• Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из КА в АРВ.
• Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ: из АРВ в КА.
• Лемма о разрастании для ДКА.
• КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Вложенность регулярных языков в КС-языки.
• Нормальная форма Хомского. Приведение к ней: удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
• Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
• Лемма о разрастании для КС-грамматик.
• Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из АМП в КСГ.
• Автоматы с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик: из КСГ в АМП.
• Иерархия Хомского.

План

Лекция 1

• Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
• Детерминированные конечные автоматы. Принятие слова.
• Эквивалентность состояний. Минимизация ДКА.
• Правые контексты.

Лекция 2

• Динамическое программирование по ДКА.
• Прямое произведение ДКА.
• Недетерминированные конечные автоматы с eps-переходами. Принятие слова.
• Детерминизация НКА.

Лекция 3

• Академические регулярные выражения.
• Теорема Клини — эквивалентность КА и АРВ.

Лекция 4

• Операции над языками. Свойства регулярных языков.
• Лемма о разрастании.

Лекция 5

• КС-грамматики.
• Вывод, левосторонний вывод, дерево разбора.
• Однозначные КС-грамматики.
• Вложенность регулярных языков в КС-языки.

Лекция 6

• КС-грамматики с АРВ в правой части.
• Нормальная форма Хомского.
• Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
• Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.

Лекция 7

• Лемма о разрастании для КС-грамматик
• Автоматы с магазинной памятью

Лекция 8

• Эквивалентность МП-автоматов и КС-грамматик
• Иерархия Хомского

Д/з №1, срок сдачи: 3 марта 2015 г., 14:10

В бумажном виде или (на большее число баллов) хорошо свёрстанное (LaTeX + tikz) по эл. почте с темой письма «SPbAU FL HW1 Your Name».

1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}:

a) множество слов, содержащих подстроку «011»;

b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на «01»;

c) множество слов, в которых нет пяти одинаковых цифр подряд.

2) Опишите HКА или ε-НКА, который распознает следующее множество слов над алфавитом {0, 1}:

a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3;

b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек «01», либо из повторяющихся несколько раз (один или более) строчек «010»;

c) множество слов, в которых на хотя бы одной из трех левых или двух правых позиций стоит единица;

3) Детерминизируйте автомат, являющийся ответом на задание 2b.

4) ... и минимизируйте результат выполнения задания 3.

Ссылки

• Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
• [1]
• [2]
• [3]
• [4]