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

Выполнить два задания:

Написать программу, которая по заданному регулярному выражению построит эквивалентный ДКА. Функция переходов ДКА может изображаться в виде таблицы и графа (выбор вида отображения посредством меню). Программа должна сгенерировать по РВ несколько цепочек в заданном диапазоне длин и проверить их допустимость построенным автоматом. Процесс разбора цепочек автоматом отображать на экране (по требованию). Предусмотреть возможность разбора цепочки, введённой пользователем. В качестве исходных данных допускаются РВ, порождающие цепочки, имеющие определенное количество циклических повторений всех символов алфавита или некоторой их части, заканчивающиеся на заданную цепочку. Например, (а+b+с)*ааса, или ((а+b)(а+b))*аасb, и т.п.

Написать программу, которая для языка, заданного контекстносвободной грамматикой в требуемой форме (проверить корректность задания и при отрицательном результате выдать соответствующее сообщение), построит детерминированный распознаватель с магазинной памятью, используя алгоритм восходящего анализа с возвратами («сдвиг-свертка»). Программа должна сгенерировать по исходной грамматике несколько цепочек в указанном диапазоне длин и проверить их допустимость построенным ДМПА. Процессы построения цепочек и проверки их выводимости отображать на экране (по требованию). Предусмотреть возможность проверки цепочки, введённой пользователем.