Курсовая работа по дисциплине: Теория языков программирования и методы трансляции. Вариант №1

Постановка задачи
Написать программу для автоматического построения детерминированного конечного автомата (ДКА) по словесному описанию языка.
Входные данные
• Алфавит языка;
• Обязательная начальная подцепочка;
• Цепочка для распознавания.
Выходные данные
• Построенный ДКА (все 5 элементов);
• Результат проверки цепочки.
Алгоритм решения задачи
 Сперва по описанию языка строится недетерминированный конечный автомат, а затем он приводится к детерминированному виду.
Рассмотрим пример построения ДКА (методом построением сначала НКА, а затем его преобразованием).
Задан язык: алфавит {0,1,a,b} и обязательная начальная подцепочка «01ab». Анализируем задание: язык будет состоять из цепочек любой длины, начинающихся на «01ab», например {01ab1a, 01abbb, 01abba1, ...}. Тогда ДКА должен иметь вид M(Q,{0,1,a,b},,q0,F), множество состояний Q и заключительные состояния F определятся в процессе построения. Разберёмся с построением функции переходов . Очевидно, что пустая цепочка в языке не содержится (поскольку есть непустая обязательная начальная цепочка). Сначала определимся с минимальной цепочкой языка – это «01ab», и построим для неё граф переходов.