Преобразование NFA для проверки электронной почты в DFA

Может ли кто-нибудь помочь в том, как преобразовать NFA для этой проверки электронной почты в DFA?

Изображение для проверки электронной почты NFA

Чтобы сделать преобразование, я сначала создал таблицу перехода состояний, а затем может ли кто-нибудь помочь создать DFA?

Таблица переходов состояний NFA


dfa nfa
person romaya    schedule 18.09.2020    source источник
comment
@ggorlen хорошо, я покажу вам, что я сделал, но не могли бы вы помочь, потому что я новичок в этом, спасибо   -  person romaya    schedule 18.09.2020
comment
@ggorlen, но проблема в том, что я НЕ МОГУ СНОВА ПУБЛИКОВАТЬ НИКАКОЕ обновление, так как вы показали изображение, каждый раз, когда я пытаюсь опубликовать что-либо, оно говорит, что у вас недостаточно репутации для изображения, которое вы только что показывали.   -  person romaya    schedule 18.09.2020
comment
@ggorlen не могли бы вы помочь?   -  person romaya    schedule 18.09.2020
comment
@ggorlen не могли бы вы обновить вопрос и помочь мне, пожалуйста   -  person romaya    schedule 18.09.2020
comment
Конечно, спасибо за попытку. Выглядит неплохо. Однако у меня есть вопрос: как a-z должен различать com и c? Например, кажется, что [email protected] не пройдет синтаксический анализ, или я не совсем понимаю, как com может быть токеном, учитывая кажущуюся односимвольную схему синтаксического анализа.   -  person ggorlen    schedule 18.09.2020
comment
Знакомы ли вы с конструкцией powerset (подмножества)?   -  person templatetypedef    schedule 18.09.2020
comment
В некоторой степени, но я не понимаю, как это связано - можете ли вы объяснить?   -  person ggorlen    schedule 18.09.2020

Ответы (1)


arrow_upward
1
arrow_downward

Создание DFA из ваших эпсилон-замыканий кажется прямым. Каждое замыкание формирует одно состояние DFA, а переходы в DFA представляют собой совокупность переходов для узлов эпсилон-замыкания NFA. Вот таблица переходов для DFA из ваших электронных закрытий:

   | a-z | 0-9 | @ | _  | .  | com
---|-----|-----|---|----|----|-----
A^ | AB  |     |   |    |    |
AB | AB  | AB  | C |    |    |
C  | CD  | CD  |   | CD |    |
CD | CD  | CD  |   | CD | CE |
CE | CD  | CD  |   | CD |    | F
F$ |     |     |   |    |    |

Вот DFA для этой таблицы (посмотреть на графике):

digraph G {
    rankdir=LR;
 
    node [shape=point]; qi;
    node [shape=doublecircle]; F;
    node [shape=circle];

    qi -> A;
    A  -> AB [label="a-z"]
    AB -> AB [label="a-z | 0-9"];
    AB -> C  [label="@"]
    C  -> CD [label="a-z | 0-9 | _"]
    CD -> CD [label="a-z | 0-9 | _"]
    CD -> CE [label="."]
    CE -> CD [label="a-z | 0-9 | _"]
    CE -> F  [label="com"]
}
person ggorlen    schedule 18.09.2020