Написать программу для автоматического построения регулярной грамматики

Zaochnik

При выполнении задания следует использовать средства объектно-ориентированного программирования. Выбор конкретного средства разработки оставляется за студентом. При наличии определённых требований к программному обеспечению студенту следует уведомлять об этом преподавателя. Написать программу для автоматического построения регулярной грамматики (леволинейной или праволинейной) по словесному описанию языка. Вход программы: алфавит языка, обязательные начальная и конечная подцепочки, тип грамматики (ЛЛ либо ПЛ), 2 числа – диапазон длин для генерации цепочек. Выход: построенная грамматика (все 4 элемента), результат генерации цепочек. Подробно: Язык задан своим алфавитом, обязательной начальной и конечной подцепочками, которые должны присутствовать во всех цепочках языка. В заданных подцепочках не должно находиться символов, не содержащихся в алфавите. В крайнем случае они (одна или обе) могут быть и пустыми. Особый случай – это пересечение заданных цепочек по одному или нескольким символам, в том числе и полное их совпадение. Программа должна: по предложенному описанию регулярного языка строить регулярную грамматику, генерирующую этот язык, в том виде, как она рассматривалась в теории, раздел 1.3.1; с помощью построенной грамматики генерировать все цепочки языка в заданном пользователем диапазоне длин. Грамматика должна строиться и праволинейная, и леволинейная. Желаемый тип грамматики выбирается пользователем в меню. Все правила грамматики должны соответствовать выбранному типу! Отдельно следует указывать, какой нетерминальный символ является целевым. Если в грамматике используется пустое правило, то необходимо дать пояснение, каким именно символом обозначается пустая цепочка. После построения грамматики пользователь может убедиться в её правильности путём генерации всех цепочек языка в том диапазоне длин, который он задаст. Генерацию каждой цепочки языка следует поэтапно отображать на экране в виде цепочки вывода (в соответствии с примерами раздела 1.4.1.). Генерация осуществляется в соответствии с лабораторной работой №1. Рассмотрим пример построения регулярной грамматики. Задан язык: алфавит {a,b,c}, обязательная начальная цепочка ‘саа’, конечная цепочка ‘aab’. Анализируем задание: язык будет состоять из цепочек любой длины, начинающихся с цепочки ‘cаа’ и заканчивающихся на ‘aab’, например {сaab, саaab, сaaааb, caaсааb, сaabaab, …}. Для определённости выберем праволинейную грамматику (ПЛ). В правой части её правил вывода может быть только один нетерминал, и он должен располагаться справа от цепочек терминальных символов. Все цепочки языка должны начинаться с заданной цепочки ‘саа’, после которой может находиться всё, что угодно. Значит, правило для целевого символа будет иметь вид: S→caaА, а для нетерминала А: А→aA|bA|cA. В конце должна быть ‘aab’, значит, выход из нетерминала А будет по ней: А→aA|bA|cA|aab. Осталось учесть возможные пересечения цепочек, это ‘сaab’, ‘саaab’. Их нужно выводить из целевого символа. Итак, грамматика имеет вид: G({a,b,c},{S,A},P,S), Р: S→caaА|сaab|саaab; А→aA|bA|cA|aab. Методичка во вложенном файле (2 вариант) В другом вложенном файле аналогичная работа другого варианта

руб. 3050 In stock