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

Задание на курсовую работу.
Написать программу для автоматического построения регулярного выражения (РВ) по словесному описанию языка.
Вход программы: алфавит языка, обязательная начальная подцепочка, выбранный символ алфавита, его кратность (натуральное число), 2 числа – диапазон длин для генерации цепочек.
Выход: построенное регулярное выражение, результат генерации цепочек.
Подробно:
Язык задан своим алфавитом, обязательной начальной цепочкой и указанием кратности вхождений некоторого символа во все цепочки языка. В начальной цепочке не должно находиться символов, не содержащихся в алфавите. В крайнем случае она может быть и пустой. Кратность числа вхождений выбранного символа задаётся любым натуральным числом. Кратность, равная единице, равносильна отсутствию ограничений на вхождения данного символа, т.е. он может встречаться в цепочках любое количество раз. При любом значении кратности количество вхождений символа в цепочку может быть и нулевым.
Программа должна:
1. по предложенному описанию регулярного языка строить РВ, генерирующее этот язык, в том виде, как было рассмотрено в теории, раздел 2.1.1;
2. с помощью построенного РВ генерировать все цепочки языка в заданном пользователем диапазоне длин.
При генерации цепочек языка по РВ можно использовать любые структуры и алгоритмы, в том числе и прямой перебор.
Рассмотрим пример построения регулярного выражения.
Задан язык: алфавит {0,1,a,b}, обязательная начальная цепочка ‘01a’, количество вхождений символа ‘а’ кратно 2. Анализируем задание: язык будет состоять из цепочек с чётным количеством символов ‘а’, начинающихся с ‘01a’, например {01аa, 01аba, 01аab, 01аac, 01аaaa,…}. Для начала определим минимально возможную цепочку этого языка. Это ‘01aa’ – она удовлетворяет всем условиям и является при этом самой короткой. Это основа нашего РВ.
Удлинить эту цепочку можно, поместив после неё или между цепочкой ’01a’ и ‘a’ в ней любое количество любых символов алфавита, за исключением символа ‘a’ – для него нужно подсчитывать количество, поэтому его следует рассматривать особо. Заданную цепочку ’01a’ разрывать нельзя. Для генерации любого количества символов используется итерация, а выбор одного из нескольких символов записывается в виде суммы.
Итак, получим 01a(0+1+b)*a(0+1+b)*. Но по построенному таким образом выражению нельзя получить много символов ‘a’. Для увеличения количества ‘a’ можно добавить после построенного выражения (aa)* для сохранения чётности. Но тогда нельзя будет между символами ‘a’ поместить другие символы алфавита. Для того чтобы сделать это возможным, заменим добавляемую конструкцию на ((0+1+b)*a(0+1+b)*a(0+1+b)*) *, сохранив чётность ‘a’ и добавив любое количество других символов. Итоговое регулярное выражение будет иметь вид:
01a(0+1+b)*a(0+1+)*((0+1+b)*а(0+1+b)*a (0+1+b))*. Можно несколько упростить построенное выражение, убрав одну из скобок (0+1+b)* – там, где она повторяется. Окончательный ответ: 01 a(0+1+b)*a(0+1+b)*(а(0+1+b)*a(0+1+b))*.

Сдано на отлично в 2023 году.