Преобразуйте следующее регулярное выражение в NFA - PullRequest
Новая
       39

Преобразуйте следующее регулярное выражение в NFA

0 голосов
/ 26 января 2020

Преобразовать следующее регулярное выражение в NFA: ab ((ba) * + a *)

1 Ответ

1 голос
/ 27 января 2020

Для этого существует изящный алгоритм, который строит NFA по одному шагу за раз на основе операций с регулярным выражением. Внешние операторы здесь - это конкатенация: ваше регулярное выражение - это конкатенация трех терминов: 

(a)(b)((ba)* + a*)

Это означает, что существует NFA, который является конкатенацией трех NFA, которые принимают язык, сгенерированный этим выражением. NFA для языков (a) и (b) тривиальны: 

L = {a}
q0--a-->q1

L = {b}
q2--b-->q3

Предположим, что позже мы получим NFA для языка (ba) * + a *, и его начальный символ q4. Тогда наш NFA будет выглядеть так (немаркированные переходы - epsilon / lambda / empty): 

q0--a-->q1----->q2--b-->q3----->q4

Мы можем повторить алгоритм для подвыражения (ba) * + a *. Самая внешняя операция здесь +; это означает, что NFA выглядит следующим образом, где q5 и q6 - начальные состояния для подвыражений слева и справа от оператора +: 

q4----->q5
 |
 |
 V
 q6

NFA для * достаточно прост: 

q6-a-\
 ^   |
 \___/

Я пропущу пару шагов и просто запишу NFA для (ba) *, но алгоритм (аналогичный тому, который используется для доказательства эквивалентности NFA и RE) также имеет простое правило для этого: 

q5--b-->q7
 ^      |
 |      a
 \______/

Если сложить все вместе, то получится: 

q0--a-->q1----->q2--b-->q3----->q4----->q5--b-->q7
                                 |       ^      |
                                 |       |      a
                                 V       \______/
                                 q6-a-\
                                  ^   |
                                  \___/
...