Теория автоматов, лабораторные работы

Лабораторная работа №1
Формальные грамматики. Выводы
Цель занятия: изучить основные понятия теории формальных языков и грамматик.
Задания
1. Написать программу, выполняющую левый (правый) вывод в заданной КС-грамматике.
Исходные данные: КС-грамматика.
Выполнение: на каждом шаге вывода отображается промежуточная цепочка (на первом шаге она представляет собой начальный нетерминал, на последнем – терминальную цепочку) и правила, которые можно применить на данном шаге. Пользователь выбирает одно из предложенных правил и процесс повторяется.
Результат: терминальная цепочка, последовательность номеров правил, участвовавших в её выводе, дерево вывода в линейной скобочной форме (ЛСФ ДВ).

Лабораторная работа №2
Преобразования КС-грамматик
Цель занятия: изучить основные эквивалентные преобразования КС-грамматик и научиться применять их для получения КС-грамматик, обладающих заданными свойствами.
Задания
1. Преобразовать исходную грамматику G (см. варианты заданий) в грамматику G1 без лишних символов.
2. Преобразовать грамматику G1 в грамматику G2 без -правил.
3. Преобразовать грамматику G2 в грамматику G3 без цепных правил.
4. Преобразовать грамматику G3 в грамматику G4 без левой рекурсии.
5. Преобразовать грамматику G4 в грамматику G5 без несаморекурсивных нетерминалов.
6. Получить грамматику G6, эквивалентную грамматике G1, в которой любые два правила с одинаковой левой частью различаются первым символом в правой части (грамматика G6 может содержать -правила).
7. Получить грамматику G7, эквивалентную грамматике G1, в которой правая часть каждого правила состоит либо из одного терминала, либо двух нетерминалов.
8. Получить грамматику G8, эквивалентную грамматике G1, в которой правая часть каждого правила начинается терминалом.

Лабораторная работа №3
Регулярные языки и конечные распознаватели
Цель занятия: изучить основные способы задания регулярных язы¬ков, алгоритмы построения, преобразования, ана¬лиза и реализации конечных распознавателей.
Задания
1. Построить минимальный детерминиро¬ванный конечный распознаватель заданного языка (см. варианты заданий).
2. Написать программу-распознаватель.
Исходные данные: строка.
Результат: “допустить” – если строка представляет собой цепочку заданного языка;
“отвергнуть” – в противном случае.

3. Написать программу, которая оставляет в исходном текстовом файле только цепочки заданного языка.
4. Написать программу, которая исключает из исходного текстового файла подстроки, являющиеся цепочками заданного языка.

Лабораторная работа №4
Лексический анализ
Цель работы: изучить и научиться применять методы разработки и реализации лексических анализаторов.
Задания
1. Построить конечные распознаватели лексем заданного языка (см. варианты заданий).
2. Определить действия, выполняемые лексическим анализатором.
3. Программно реализовать лексический анализатор заданным методом в виде подпрограммы. При обнаружении лексической ошибки лексический анализатор должен выдавать сообщение о типе ошибки и её расположении (номер строки) в исходном тексте.
4. Написать программу, преобразующую исходный текст программы на заданном языке в таблицу лексем.
5. Обработать исходные тексты, содержащие и несодержащие лексические ошибки.
other-любая цифра и буква английского алфавита
б- английская буква (любого регистра), ц- цифра