Как объединить соседние символы звездочек Клини из алфавита? - PullRequest
Новая
       107

Как объединить соседние символы звездочек Клини из алфавита?

0 голосов
/ 25 мая 2020

Я столкнулся с ситуацией, когда мне нужно преобразовать регулярные выражения в диаграммы NFA с языка {1,0}. В регулярном выражении я обнаружил, что есть два конкатенированных символа со звездами Клини, 1*0*. В основном это означает, что строка имеет любое количество единиц, за которыми следует любое количество нулей.

При преобразовании в NFA я запутался, главным образом потому, что есть две транзакции, указывающие наружу от первого символа (1*) состояние accept: транзакция эпсилон возвращается в исходное состояние (потому что она имеет звезду Клини) и транзакция эпсилон возвращается в исходное состояние 0*.

Я не уверен, 1) могу ли я иметь две транзакции, выходящие из одного и того же состояния при преобразовании в NFA, и если да, 2) как упростить эту транзакцию.

Любая помощь будет принята с благодарностью!

1 Ответ

0 голосов
/ 25 мая 2020

У вас определенно может быть несколько переходов эпсилон из одного и того же состояния.

Использование https://en.wikipedia.org/wiki/Thompson%27s_construction,

Конкатенация s и t: начальное состояние s - новое начальное состояние, принимающее состояние t - это новое принимающее состояние. Состояние принятия s становится начальным состоянием t.

Клини-закрытие s: введите новое начальное состояние и новое состояние принятия. Добавьте эпсилон-переход от начального состояния к конечному состоянию. Добавьте эпсилон-переход от нового начального символа к исходному, и эпсилон-переход от исходного принятия к новому принятию, а также эпсилон-переход от исходного принятия к исходному начальному. : 1* в сочетании с 0*.

1 само по себе - это просто q --1--> f. Преобразование Kleene в NFA дает 

/--------------e--------------\
|                             V
q --e--> q1 --1--> q1f --e--> f
          ^        |
          \---e----/

с аналогичной конструкцией для 0*. Чтобы объединить их, возьмите состояние принятия из первого и определите его как начальное состояние для второго: 

/---------------e-------------\  /-------------e---------------\
|                             V  |                             V
q --e--> q1a --1--> q1f --e--> q0 --e--> q0a --0--> q0f --e--> f
          ^          |                    ^          |
          \-----e----/                    \-----e----/

Для упрощения вы можете преобразовать его в NFA или DFA, используя соответствующее преобразование. алгоритмы.

...