Как я могу проверить, соответствует ли моя линия NFA?

Я сделал NFA, который делает из регулярных выражений 3d-массив, например (01*) выражение. Я понимаю:

[[FROM,TO,TRANSITION]]

    [['q0', 'q1', '0'], ['q1', 'q2', ':e:'] ,['q1', 'q4', ':e:'] ,
    ['q2', 'q3', '1'], ['q3', 'q2', ':e:'], ['q3', 'q4', ':e:']

Как мне написать метод, который может проверить строку, удовлетворяющую этому автомату? Например, "011111" вернет q0 q1 q2 q3 q2 q3 q2 q3 q2 q3 q2 q3 q4.


python algorithm automaton nfa
person Eywa    schedule 16.04.2017    source источник
comment
А знали бы вы, как это сделать, если бы автомат был детерминированным?   -  person timgeb    schedule 16.04.2017
comment
(если да, примените поисковую систему foo для алгоритма построения DFA)   -  person timgeb    schedule 16.04.2017
comment
Существует множество существующих библиотек, которые вы могли бы использовать, поэтому вам не нужно заново изобретать колесо. Я бы предложил brics.dk/automaton, мощный и простой в использовании пакет автоматов. для Явы. Он делает именно то, что вы хотите. Также довольно легко расширить класс Automaton, если вам нужна дополнительная информация о том, какие именно переходы были выполнены для соответствия заданной строке.   -  person Julian    schedule 16.04.2017
comment
Являются ли переходы :e: epsilon? Кажется, что q4 — это принимающее состояние, но где это выражается?   -  person Paul Hankin    schedule 16.04.2017
comment
Пол Хэнкин, извини, я забыл об этом. Вы правильно написали   -  person Eywa    schedule 16.04.2017

Ответы (1)


arrow_upward
1
arrow_downward

  1. Вы можете преобразовать автомат в DFA (после этого проверка становится тривиальной). Этот подход полезен, если NFA невелик, но количество строк, которые вы собираетесь тестировать, довольно велико.

  2. Также можно построить новый граф, где каждая вершина является парной (состояние NFA, позиция в строке). Существует граница между состоянием и другим состоянием для каждой позиции, если это эпсилон-переход. Также есть ребро (s, pos) -> (s', pos + 1), если символ перехода s->s' в автомате совпадает с символом в позиции pos в строке.
    После построения графа вам достаточно проверить, что пара (t, string.length()) достижима хотя бы для одного конечного состояния t (для проверки можно использовать любой алгоритм обхода графа, например поиск в глубину).

person kraskevich    schedule 16.04.2017