Разработка DFA - PullRequest
Новая
       72

Разработка DFA

0 голосов
/ 30 мая 2019

Я хочу создать DFA для следующего языка после устранения неоднозначности. Я много думал и старался, но не смог получить правильный ответ. 

S->aA|aB|lambda
A->aA|aS
B->bB|aB|b

1 Ответ

0 голосов
/ 03 июня 2019

Я рекомендую сначала получить NFA, считая это обычной грамматикой;затем определите NFA, и затем мы можем записать новую грамматику, которая эквивалентна этой, но однозначной (по той же причине детерминированный автомат является детерминированным).Записать NFA для этой грамматики легко: произведения вида X -> sY преобразуются в переходы из состояния X в состояние Y на входе s.Аналогично, переходы в форме X -> lambda mean X являются принимающим состоянием, а переходы в форме X -> b подразумевают новое принимающее состояние, которое переходит в мертвое состояние.

Нам нужны состояния для каждого нетерминаласимвол S, A и B;и у нас будут переходы для каждого производства.Наш NFA выглядит следующим образом: 

       /---a----\
       |        |
       V        |
----->(S)--a-->(A)<--\
       |        |    |
       a        \--a-/   /--a,b--\
       |                 |       |
       V                 V       |
 /--->(B)--b-->(X)-a,b->(Y)<-----/
 |     |
 \-a,b-/

Здесь, состояния (S) и (X) принимают, состояние (Y) является мертвым состоянием (нам не нужно было это явно отображать, но имейте в видусо мной), и этот автомат полностью эквивалентен грамматике.Теперь нам нужно определить это.Состояния детерминированного автомата будут соответствовать подмножествам состояний из недетерминированной версии.Наше первое детерминированное состояние будет соответствовать набору, содержащему только (S), и мы выясним другие необходимые подмножества (из которых у нас может быть не более 32, так как у нас есть 5 состояний и 2 в степени 5 равно 32), используяпереходы: 

Q               s    Q'
{(S)}           a    {(A),(B)}
{(S)}           b    empty
{(A),(B)}       a    {(A),(B),(S)}
{(A),(B)}       b    {(B),(X)}
{(A),(B),(S)}   a    {(A),(B),(S)}
{(A),(B),(S)}   b    {(B),(X)}
{(B),(X)}       a    {(B),(Y)}
{(B),(X)}       b    {(B),(X),(Y)}
{(B),(Y)}       a    {(B),(Y)}
{(B),(Y)}       b    {(B),(X),(Y)}
{(B),(X),(Y)}   a    {(B),(Y)}
{(B),(X),(Y)}   b    {(B),(X),(Y)}

Мы столкнулись с шестью состояниями плюс мертвое состояние (empty), которое мы можем назвать от q1 до q6, плюс qD.Все состояния, соответствующие подмножествам с (S) или (X) в них, принимаются, а (S) является начальным состоянием.Наш DFA выглядит следующим образом: 

                  /-a,b-\
                  |     |
                  V     |
----->(q1)--b-->(qD)----/
       |
       a          /--a--\
       |          |     |
       V          V     |
      (q2)--a-->(q3)----/
       |         |
       b         |
       |         b
       V         |
  /--(q4)<------/     /--b--\
  |   |               |     |
  |   \------b------(q6)<---+
  a     /--a----\    |      |
  |     |       |    |      |
  \-->(q5)<-----+--a-/      |
        |                   |
        \---------b---------/

Наконец, мы можем прочитать однозначную регулярную грамматику из нашего DFA: 

(q1) -> a(q2) | b(qD) | lambda
(qD) -> a(qD) | b(qD)
(q2) -> a(q3) | b(q4)
(q3) -> a(q3) | b(q4) | lambda
(q4) -> a(q5) | b(q6) | lambda
(q5) -> a(q5) | b(q6)
(q6) -> a(q5) | b(q6) | lambda
...