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

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

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

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

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

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

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

    Автомат, распознающий такие цепочки приведен на рисунке:
    nondeterministic-finite-state-machine
    Цепочка принадлежит языку если для нее существует путь из узла 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 описывает все возможные условия переходов.

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