Программирование задачи

Задача 2 (Поиск пересечения языка образцов с языком, описанным регулярным выражением).

Пусть заданы алфавит констант ? и алфавит строковых переменных V. Плоский образец — это строка P, где P ? ? ? V?. Язык образца L(P) — это все слова w ? ?? такие, что ?? : V ? ??(w = P?).

Известно, что языки образцов являются подмножеством контекстнозависимых языков, не включающим все регулярные языки. Поэтому в некоторых алгоритмах анализа (программ либо данных) естественно использовать оба языка совместно. Для этого необходим алгоритм построения возможного множества регулярных рестрикций на языки переменных из имеющихся рестрикций на язык образца целиком.

Задача

По исходному паттерну P(x1, . . . , xk) и множеству регулярных рестрикций {P in Ri} построить множество регулярных рестрикций на переменные xi, входящие в P.

Входные данные программы — следующие четыре строки.

{a1,...,an}

{x1,...,xm}

P

+ | empty

В первой строчке (в фигурных скобках, через запятую) задается алфавит констант ? (если он содержит пробел, круглые скобки или знаки #, * или |, выдаем сообщение об ошибке); во второй — алфавит переменных V. В третьей — образец, записанное в заданном алфавите. Четвертая строчка либо содержит сообщение, что регулярных ограничений нет (empty), либо содержит список регулярных ограничений на образец U. Регулярные ограничения записываются в синтаксисе r ::= # | ai | r1r2 | (r1 | r2) | (r)?, где # — обозначение для пустой строки ?. Результатом работы алгоритма должно быть описание регулярных рестрикций на переменные, входящие в P.

Решение на 4: произвольное множество рестрикций, решение на 5:

множество рестрикций упрощено согласно алгебраическим преобразованиям над языком регулярных выражений.

необходимо написать код программы

Входные данные в приложенном файле