Недетерминированный конечный автомат на Prolog

      Комментарии к записи Недетерминированный конечный автомат на Prolog отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 3 мес., 4 нед. назад.

  • Автор
    Сообщения
  • #3240

    Введение

    В настоящей работе реализуется недетерминированный магазинный автомат. Сергиевский в 20 главе своей книги [1] отмечал удобство использования логического программирования при реализации автоматов, т. к. с помощью фактов удобно описывать правила переходов, а встроенный в пролог механизм поиска с возвратами позволяет без труда реализовать перебор состояний (поиска последовательности состояний, обеспечивающих распознавание).
    В качестве языка программирования для выполнения курсовой работы выбран Visual Prolog 5.2, т. к. в отличии от многих других реализаций Пролога, таких как SWI Prolog, GNU Prolog, Arity Prolog и т. п., в комплект поставки входит среда разработки, включающая отладчик. При этом, в отличии от более современных версий Visual Prolog, версия 5.2 запускается не только на платформе Windows, но и на Linux (с использованием wine).
    Целью работы является разработка программы распознавания грамматики и получение практических навыков программирования на языках логической парадигмы. Актуальность работы обусловлена тем, что:

    • задача распознавания предложений, принадлежащих грамматике, возникает достаточно часто — например, в любом компиляторе или интерпретаторе языка программирования;
    • решение задачи с использованием автоматов проще поддается отладки и формальной верификации, т. к. модель автомата проще модели обычного компьютера [2].

    Задачами работы являются:

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

    Решение первой задачи обуславливает теоретическую ценность работы, а вторая и третья — практическую.

    Постановка задачи

    Написать на языке Prolog программу, реализующую недетерминированный магазинный автомат для распознавания предложений, порождаемых грамматикой (a)n(b)n, (n >= 0).
    Примерами входных предложений, соответствующим грамматике могут быть:

    «aabb»;
    «ab»;
    «».

    Примерами предложений, не соответствующих грамматике являются:

    «abba»;
    «abb»;
    «abb»;
    «aabbc».

    Разработка автомата

    Для решения задачи необходимо выделять из исходной последовательности символы «a», если за ними будет следовать такое же количество символов «b». Если при этом строка окажется пустой — то она соответствует грамматике. Таким образом нужно «вычислить» количество символов «a», однако, автоматы могут лишь осуществлять переходы из одного состояния в другое без выполнения вычислений. Автоматы с магазинной памятью позволяют поместить данные в магазин, представляющий собой стек.
    При решении этой задачи мы можем помещать в магазин какой-либо символ при считывании последовательности из «a», а затем, при считывании «b» — удалять символы из магазина. При этом количество символов, помещенных в магазин будет соответствовать N из условия задачи, записанной в унарной системе счисления.
    Автомат, решающий задачу приведен на рисунке 1. При этом:

    • начальные и конечные состояния обозначены как begin и end;
    • в состоянии «1» автомат считывает последовательность символов «a», а в «2» — символов «b».
    • переходы обозначены в соответствии с правилом:

      <символ строки>, <символ магазина>:<новый символ магазина>

    • символом ε обозначается отсутствие символа.

    nondeterministic-finite-state-machine

    Таким образом, автомат, находясь в начальном состоянии может перейти только в состояние «1» если во входной строке находится символ «а» и магазин пуст, при этом в магазин записывается символ «а». Из состояния «1» выполняется переход в состояние «1» если во входной строке встретился символ «а» и в магазине находится символ «а», — при таком переходе в магазин помещается «аа», т. к. один символ из магазина обязательно будет удален.

    Разработка программы на Prolog

    Разработка программы на языке Visual Prolog начинается с определения используемых типов в разделе domais. В нашем случае необходимо определить тип символа исходной последовательности (цепочки), тип самой цепочки (список символов), тип магазина (также список символов, хотя мы могли бы помещать туда любые символы — важно лишь количество, ведь магазин фактически хранит число в унарной системе счисления) и набор состояний:

    DOMAINS 
      символ = char
      цепочка = символ*
      магазин = символ*
      состояние = начальное_состояние; конечное_состояние; группа_а; группа_б
    Листинг 1 типы данных программы
    	Затем, в разделе predicates нужно описать прототипы используемых функций:
    PREDICATES
      nondeterm переход(состояние, состояние, цепочка, цепочка, магазин, магазин)
      nondeterm автомат(состояние, цепочка, магазин)
      распознаватель(цепочка)
      
      string_to_list(string, цепочка)

    В данном случае предикаты «переход» и «автомат» обозначены как nondeterm. Функция переходов будет состоять из набора правил, а значит, вызов этого предиката может дать несколько различных решений. Функция «автомат» реализует логику автомата с магазинной памятью — она является недетерминированной из за того, что реализует недетерминированный автомат.
    Функция string_to_list(string, цепочка) выполняет преобразование строки в список символов. Она необходима в связи с тем, что пользователь будет вводить строку, но в Visual Prolog она представляется особым типом данных, поэтому для удобства обработки ее можно сначала преобразовать в список. Стоит отметить, что в SWI Prolog такое преобразование не потребуется, т. к. тип строки в нем представляется списком. Для считывания символов из строки используется встроенная функция frontchar, работа функции сводится к извлечению символов из начала строки и помещения их в начало списка рекурсивно. Реализация функции помещается в секции clauses:

      string_to_list("", []):-!.
      string_to_list(String, [Head|ListTail]):-
        frontchar(String, Head, StringTail),
        string_to_list(StringTail, ListTail).

    Распознавание строки выполняется функцией «распознаватель», которая лишь запускает автомат из начального состояния, передавая в него исходную строку:

      автомат(конечное_состояние, _Цепочка, _Магазин).
      автомат(Состояние, Цепочка, Магазин):-
        переход(Состояние, НовоеСостояние, 
                Цепочка, НоваяЦепочка, 
                Магазин, НовыйМагазин),
        автомат(НовоеСостояние, НоваяЦепочка, НовыйМагазин).
    
      распознаватель(Цепочка):-
        автомат(начальное_состояние, Цепочка, []), !.

    Предикат «автомат» завершает вычисления если оказывается в конечном состоянии, в противном случае он обращается к функции перехода для получения нового состояния, цепочки и магазина, и рекурсивно выполняет запуск автомата из нового состояния с новыми параметрами. За счет встроенного в пролог механизма поиска с возвратами будут перебраны все возможные переходы.

      переход(начальное_состояние, группа_а, 
              ['a'|Цепочка], Цепочка,  [], ['a']).
      переход(начальное_состояние, конечное_состояние, 
              [], [], [], []).
      переход(группа_а, группа_а, 
              ['a'|Цепочка], Цепочка, ['a'|Магазин], ['a', 'a'|Магазин]).
      переход(группа_а, группа_б, 
              ['b'|Цепочка], Цепочка, ['a'|Магазин], Магазин).
      переход(группа_б, группа_б, 
              ['b'|Цепочка], Цепочка, ['a'|Магазин], Магазин).
      переход(группа_б, конечное_состояние, 
              [], [], [], []).

    Функция перехода содержит по одному правилу на каждую дугу графа автомата. Так например, последнее правило описывает переход из состояния чтения группы символов «b» в конечное состояние при условии что магазин пуст и исходная строка больше не содержит символов.
    Выполнение программы начинается с кода, помещенного в секцию goal, которая является точкой входа:

     GOAL    
      write("enter the sequence: "),
      readln(Строка),
      string_to_list(Строка, Цепочка),
      распознаватель(Цепочка),
      write("your string is accepted by (a)^n(b)^n"), nl, !;
      write("your string is NOT accepted by (a)^n(b)^n"), nl.

    В данном случае программа после запуска запрашивает у пользователя строку, преобразует ее в список символов и подает на распознаватель. Если распознаватель вернет true (завершится успешно) – то будет выведено первое сообщение и выполнен оператор отсечение, запрещающий передачу управления коду, расположенному после точки с запятой. Если же распознаватель вернет fail – то выполнится код, расположенный после точки с запятой (оператор “точка с запятой” соответствует логическому ИЛИ-НЕ), при этом будет выведено второе сообщение.

    Руководство пользователя для прикладной программы

    Интерфейс программы является консольным. После запуска от пользователя требуется ввести строку с цепочкой для распознавания. Результат распознавания будет выведен на экран в виде текстового сообщения.

    Для запуска программы таким образом, чтобы выполнение начиналось с секции goal, необходимо выполнять его комбинацией Ctrl+G.

    Заключение

    В данной курсовой работе была решена задача разработки программы распознавания грамматики на языке Prolog, при этом были получены:
    теоретические сведения об автоматном программировании, грамматиках и логической парадигме;
    практические навыки разработки и отладки программ в среде Visual Prolog.

    Список литературы

    1. Сергиевский Г. М. Функциональное и логическое программирование : [учеб. пособие] / Г. М. Сергиевский, Н. Г. Волченков. – М. : Академия, 2010. – 317с.
    2. Шалыто А. А. Автоматное программирование /Труды конференции «Технические и программные средства систем управления, контроля и измерения» (УКИ`10). М.: Институт проблем управления им. В.А. Трапезникова РАН. 2010, c.156 –167.

    Реализация на SWI Prolog

    Рассмотрим реализацию на SWI Prolog недетерминированного конечного автомата, распознающего язык, в котором за цепочкой из n символов a следует цепочка из n символов b. Примеры фраз такого языка: пустая строка, «ab», «aabb». Ему не принадлежат фразы «aba», «abab».

    В данной задаче нужно посчитать количество символов «a» в начале строки — N, а затем считать N символов «b». Однако, автомат не может ничего считать (он не умеет складывать). Автомат без памяти вообще не может решить эту задачу — все что он может — переходить из одного состояния в другое при некоторых условиях (входных данных и текущего состояния).

    Автомат с магазинной памятью также не умеет складывать числа, однако у него есть магазин (построенный по типу стека), в который можно помещать считанные символы. Суть нашего алгоритма будет заключаться в том, что мы считаем символы «a» и поместим их в магазин, а затем будем считывать символы «b», удаляя по одному символу из магазина. Если в один момент получится, что магазин пуст и строка тоже — значит входная последовательность принадлежит языку.

    Автомат, распознающий такие цепочки приведен на рисунке выше.
    Цепочка принадлежит языку если для нее существует путь из узла begin в узел end. На дугах показаны условия перехода в формате:
    символ строки, верхний символ автомата, новый символ автомата
    При обработке символа из строки и из автомата удаляется указанный символ, поэтому чтобы добавить символ в автомат, мы вынуждены указывать не один, а два новых символа. Символом ε в таких диаграммах традиционно показывается пустая входная строка или пустой автомат.

    Программа, соответствующая автомату:

    transit(start_state, state_a, [a|Strip], Strip, [], [a]).
    transit(start_state, finish_state, [], [], [], []).
    transit(state_a, state_a, [a|Strip], Strip, [a|Magazin], [a, a|Magazin]).
    transit(state_a, state_b, [b|Strip], Strip, [a|Magazin], Magazin).
    transit(state_b, state_b, [b|Strip], Strip, [a|Magazin], Magazin).
    transit(state_b, finish_state, [], [], [], []).
    
    machine(finish_state, _Strip, _Magazin).
    machine(State, Strip, Magazin):-
      transit(State, NextState, Strip, NewStrip, Magazin, NewMagazin),
      machine(NextState, NewStrip, NewMagazin).
    
    recognize(Chain):-
      machine(start_state, Chain, []), !.

    Функция recognize принимает цепочку символов (список), которую передает в функцию machine вместе с начальным состоянием и пустым исходным автоматом.
    Функция machine успешно завершает работу если достигнуто конечное состояние, а в противном случае выполняет переход из текущего состояния. Совершить переход — значит считать входной символ и получить новое состояние (узел автомата и состояние магазина). Если переход совершить не удалось — функция завершается неудачей.
    Функция transit описывает все возможные условия переходов.

Для ответа в этой теме необходимо авторизоваться.