Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп, страница 20

Например, выражения можно задать так:((7 + 15 - 3 X) / X)+(X /(5 X ↑ 8)), и в результате будетвычислено выражение(110 X ↑ 8 – 15 X ↑ 9 + X ↑ 2) / (5 X ↑ 9) , илис учётом упрощения: (110 X ↑ 6 – 15 X ↑ 7 + 1) / (5 X ↑ 7)В полном решении задачи на вход программы поступают текстырациональных выражений без лишних скобок, а числа, буквы переменныхи знаки операций могут не разделяться пробелом, например: X/5X↑8.105Преобразование формулы алгебры логики в ДНФПреобразовать в сокращенную дизъюнктивную нормальную формупроизвольную формулу алгебры логики, в которой используютсялогические константы, однобуквенные переменные и операциилогического отрицания, конъюнкции, дизъюнкции и импликации.Результирующая дизъюнктивная нормальная форма должна бытьправильной, т.е.

каждая её элементарная конъюнкция не должна содержатьповторных вхождений переменных, и все конъюнкции должны бытьразличными. Полученная формула не должна содержать избыточныхскобок.Например,формула(¬A∨D∨FALSE)⊃¬(B&¬C∨D)преобразуется к виду A&¬D∨¬B&¬D∨C&¬D .В упрощённом решении задачи при записи исходной логическойформулы знаки логических операций, константы и переменныеразделяются пробелами (если только между ними не стоит другойразделитель – круглая скобка), а сама формула заключается в объемлющиескобки (чтобы сделать её лисповским списком и упростить её ввод ипреобразование), например: (A ⊃ (B & ¬ C ∨ D))В полном решении задачи на вход программы поступает текстформулы, который обычно не содержит объемлющих скобок и в которомвсе символы могут быть записаны слитно.Построение по ДНФ равносильной ей КНФПо заданной дизъюнктивной нормальной форме некоторойбулевской функции построить ее совершенную конъюнктивнуюнормальную форму, а также сокращенную конъюнктивную нормальнуюформу.

Как исходная дизъюнктивная нормальная форма, так ирезультирующие конъюнктивные нормальные формы предполагаютсяправильными, т.е. все переменные, встречающиеся в каждой элементарнойконъюнкции/дизъюнкции, различны, а также нет одинаковыхэлементарных конъюнкций/дизъюнкций. В совершенной КНФ каждаяэлементарная дизъюнкция содержит вхождения всех переменныхбулевской функции, в сокращённой форме это не требуется.В исходной ДНФ используются только однобуквенные переменные.Построенные КНФ не должны содержать избыточных скобок. Например,для ДНФ A∨B&¬C получается сокращённая КНФ (A∨B)&(A∨¬C) исовершенная КНФ (A∨B∨C)&(A∨B∨¬C)&(A∨¬B∨¬C).В упрощённом решении задачи при записи исходной ДНФ знакилогических операций и переменные разделяются пробелами, а сама ДНФзаключается в объемлющие скобки (чтобы сделать её списком и упроститьеё ввод и обработку).

В полном решении задачи на вход программы106подаётся запись ДНФ без объемлющих скобок, в которой символыпеременных и знаки операций могут быть записаны слитно.Сколемизация формулы исчисления предикатовПреобразовать в предварённую нормальную форму правильнуюзамкнутую формулу исчисления предикатов первого порядка, в которойиспользуютсяпеременные, предикаты, кванторыобщности исуществования, а также логические операции (конъюнкция, дизъюнкция,импликация, отрицание). Переменные и предикаты исходной формулыпредикатов имеют однобуквенные имена.Преобразование включает следующие этапы:1) исключение операции импликации;2) уменьшение области действия операции отрицания;3) исключение кванторов существования путем сколемизации, т.е.введения функций Сколема;4) вынесение кванторов общности в начало формулы.Получаемая в результате этих преобразований формула включаетпрефикс – цепочку кванторов общности и основу (матрицу), несодержащую кванторы.

В этой формуле должны быть удалены всеизбыточные (не влияющие на порядок выполнения операций) скобки.Например, формула ∀x(P(x)⊃¬(∃y(Q(x,y)⊃P(y))))преобразуется к виду: ∀x(¬P(x)∨Q(x,g(x)) & ¬P(g(x))), гдеg(x) – функция Сколема.Предполагается, что в исходной формуле исчисления предикатовкаждый квантор общности и существования связывает переменную суникальным именем – поэтому для преобразования в предварённуюнормальную форму нет необходимости производить переименованиепеременных с одним именем, но связываемых разными кванторами.Учесть также, что в формуле могут быть опущены незначащие скобки, т.е.скобки, не изменяющие порядка выполнения операций.В упрощённом решении задачи при записи исходной формулыпредикатов знаки логических операций, кванторов, имена переменных ипредикатов разделяются пробелами, а сама формула заключается вобъемлющие скобки (чтобы сделать её лисповским выражением и темсамым облегчить её ввод и преобразование).

В полном решении задачи навход программы подаётся запись формулы, в которой нет объемлющихскобок, а все символы имён переменных, предикатов, кванторов иопераций могут быть записаны слитно.107Построение конечного автомата по грамматикеПо заданному тексту регулярной (леволинейной или праволинейной)формальной грамматики построить соответствующий конечный автоматдля распознавания предложений языка, порождаемого этой грамматикой.Грамматика задаётся как конечный набор правил вида T = aN|b,альтернативы в правых частях правил не могут быть пустыми.Нетерминальные символы грамматики записываются заглавными(большими) латинскими буквами, а терминальные – строчными(маленькими). Начальный символ грамматики обозначается буквой H(для праволинейной) или S (для леволинейной грамматики).Построенный автомат представляет собой ориентированный ипомеченный граф. Вершины графа соответствуют состояниям автомата ипомечены нетерминальными символами грамматики; в множество вершинвходит начальное состояние H и заключительное состояние S.

Рёбра графасоответствуют переходам между состояниями автомата и помеченытерминальными символами грамматики. Граф записывается в виде спискавходящих в него рёбер, каждое ребро представлено трехэлементнымсписком вида (метка_вершины метка_ребра метка_вершины).В упрощённом решении задачи при записи исходной грамматикиможно заключить в круглые скобки каждое её правило и составить из нихлисповский список, в котором все символы грамматики разделеныпробелами, а знак | и строчные буквы записаны как особые символыязыка Лисп.

Например:((H = \a N \| \b N) (N = \c N \| \d)).В полном решении задачи на вход программы подаётся текстграмматики без разделяющих пробелов, при этом правила грамматикиразделены точкой с запятой, к примеру: H=aN|bN;N=cN|d. В случаенедетерминированности полученного по грамматике автомата необходимопостроитьэквивалентныйемудетерминированныйавтомат(детерминированный автомат, распознающий тот же самый язык).Построение регулярной грамматики по конечному автоматуПо заданному конечному автомату восстановить соответствующуюрегулярную леволинейную (или праволинейную) формальную грамматику,включающую алфавиты (множества) терминальных и нетерминальныхсимволов и набор правил грамматики, а также начальный символграмматики: H (для праволинейной) или S (для леволинейной) .Конечный автомат задан как ориентированный граф, вершиныкоторогосоответствуютсостояниямавтоматаипомеченынетерминальными символами грамматики.

В множество вершин входит108начальное состояние H и заключительное S. Рёбра графа соответствуютпереходам между состояниями автомата и помечены терминальнымисимволами грамматики. Граф записан как лисповский список входящих внего рёбер, каждое ребро представлено трёхэлементным списком вида(метка_вершины метка_ребра метка_вершины).В записи восстановленной по конечному автомату грамматикинетерминальные символы грамматики записываются заглавными(большими) латинскими буквами, а терминальные – строчными(маленькими). Правая и левая часть каждого правила разделяются знаком=, а сами правила – знаком ; , в полученном тексте нет пробелов,например: В=aN|bN;N=cN|d.Исходный конечный автомат может быть как детерминированным,так и недетерминированным.

В полном решении задачи в случаенедетерминированности автомата необходимо построить, кромеграмматики,эквивалентныйемудетерминированныйавтомат(детерминированный автомат, распознающий тот же самый язык).Исследование свойств графаДля заданного графа провести исследование трёх его свойств,выбрав по одному свойству из трёх следующих групп:1) – Связность графа: в случае связности графа необходимо найти егокаркас, в ином случае – все его компоненты связности;– Древесность графа: является ли граф деревом или лесом, в последнемслучае найти составляющие его деревья;2) – Двудольность графа; если граф двудольный, то необходимоопределить, является ли он полным двудольным графом;– Существование в графе мостов и точек сочленения, в случаесуществования найти их количество;3) – Является ли граф эйлеровым, и если да, то найти эйлеров цикл;– Является ли он гамильтоновым, и если да, то найти гамильтонов цикл.Каркас графа есть наименьшее по числу рёбер входящее в негодерево, сохраняющее связность между всеми его вершинами.

Следуетучесть, что в общем случае каркас в графе находится неоднозначно.Дерево есть связный граф, не имеющий циклов. Совокупностьнесвязанных деревьев есть лес.Граф называется двудольным (биграфом), если множество еговершин допускает разбиение на два непересекающихся подмножества(доли), причём каждое ребро графа соединяет вершины из разных долей.Двудольный граф есть полный двудольный граф, если каждая вершинаодной доли соединена ребром с каждой вершиной другой доли. Граф109двудолен тогда и только тогда, когда все простые циклы в нём имеютчётную длину.Мостом называется ребро, удаление которого увеличивает числокомпонентов связности графа.

Точка сочленения – вершина, удалениекоторой ведёт к увеличению количества компонентов связности;Замкнутый путь (цикл) в графе называется эйлеровым, если онпроходит через каждое ребро графа; при этом граф с таким цикломназывается эйлеровым. Цикл в графе называется гамильтоновым, если онсодержит все вершины графа ровно по одному разу; граф с таким цикломназывается гамильтоновым.Исследуемый граф записывается как лисповский список входящих внего рёбер, а каждое ребро – как двухэлементный список из меток еговершин.