Как преобразовать NFA в регулярное выражение

Я знал, что для преобразования регулярного выражения в NFA существует алгоритм.

Но мне было интересно, есть ли алгоритм для преобразования NFA в регулярное выражение. Если есть, то что это?

А если нет, мне также интересно, могут ли все NFA конвертироваться в регулярное выражение. Существует ли NFA, который не может быть представлен регулярным выражением?

Благодарю вас! :D


regex formal-languages nfa
person formatjam    schedule 09.02.2012    source источник
comment
Регулярное выражение может выражать любой регулярный язык, поэтому должно существовать по крайней мере одно регулярное выражение для каждого возможного NFA. Однако я не знаю алгоритма перехода от NFA к регулярному выражению.   -  person Tikhon Jelvis    schedule 09.02.2012
comment
Кроме того, ваш выбор времени на самом деле жуткий — мой друг задал мне точно такой же вопрос сегодня на уроке. Я тогда тоже не запомнил ответ :(   -  person Tikhon Jelvis    schedule 09.02.2012
comment
См. множество ответов на ваш вопрос здесь: cs.stackexchange.com/questions/2016/   -  person Masterfool    schedule 15.11.2014

Ответы (1)


arrow_upward
8
arrow_downward

Вот алгоритм, в котором каждый переход постепенно заменяется регулярным выражением, пока не останется только начальное и конечное состояние: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf [PDF]

person buzypi    schedule 09.02.2012
comment
это правильно, но это не работает, если у вас много узлов, это хорошо для простых и нескольких узлов, есть ли какие-либо другие предложения? - person Mostafa Jamareh; 23.10.2013
comment
Ссылка мертва для меня. Я нашел эту ссылку: courses.engr.illinois.edu/cs373/ sp2009/лекции/lect_08.pdf - person Justin Lessard; 30.05.2015