Konstrukcja FA z RE

Możemy użyć konstrukcji Thompsona, aby znaleźć skończony automat z wyrażenia regularnego. Zmniejszymy wyrażenie regularne do najmniejszych wyrażeń regularnych i przekonwertujemy je na NFA, a na koniec na DFA.

Oto kilka podstawowych wyrażeń RA -

Case 1 - Dla wyrażenia regularnego `` a '' możemy skonstruować następujący FA -

Case 2 - Dla wyrażenia regularnego „ab” możemy skonstruować następującą FA -

Case 3 - Dla wyrażenia regularnego (a + b) możemy skonstruować następujący FA -

Case 4 - Dla wyrażenia regularnego (a + b) * możemy skonstruować następującą FA -

metoda

Step 1 Skonstruuj NFA z null ruchami z podanego wyrażenia regularnego.

Step 2 Usuń przejście o wartości Null z NFA i przekonwertuj je na jego odpowiednik DFA.

Problem

Zamień następujący RA na jego odpowiednik DFA - 1 (0 + 1) * 0

Solution

Połączymy trzy wyrażenia „1”, „(0 + 1) *” i „0”

Teraz usuniemy εprzejścia. Po usunięciuε przejścia z NDFA, otrzymujemy:

Jest to NDFA odpowiadający RE - 1 (0 + 1) * 0. Jeśli chcesz przekształcić go w DFA, po prostu zastosuj metodę konwersji NDFA na DFA omówioną w rozdziale 1.

Skończone automaty z zerowymi ruchami (NFA-ε)

Automat skończony z zerowymi ruchami (FA-ε) przechodzi nie tylko po wprowadzeniu danych z zestawu alfabetu, ale także bez żadnego symbolu wejściowego. To przejście bez wejścia nazywa się anull move.

NFA-ε jest formalnie reprezentowane przez 5-krotkę (Q, ∑, δ, q 0 , F), składającą się z

  • Q - skończony zbiór stanów

  • - skończony zbiór symboli wejściowych

  • δ- funkcja przejścia δ: Q × (∑ ∪ {ε}) → 2 Q

  • q0- stan początkowy q 0 ∈ Q

  • F - zbiór stanów / stanów końcowych Q (F⊆Q).

Powyższe (FA-ε) akceptuje zestaw ciągów - {0, 1, 01}

Usunięcie ruchów zerowych z automatów skończonych

Jeśli w NDFA jest ϵ-ruch między wierzchołkiem X a wierzchołkiem Y, możemy go usunąć, wykonując następujące kroki -

  • Znajdź wszystkie krawędzie wychodzące z Y.
  • Skopiuj wszystkie te krawędzie zaczynając od X bez zmiany etykiet krawędzi.
  • Jeśli X jest stanem początkowym, uczyń Y również stanem początkowym.
  • Jeśli Y jest stanem końcowym, uczyń X również stanem końcowym.

Problem

Konwertuj następujące NFA-ε na NFA bez ruchu Null.

Solution

Step 1 -

Tutaj przejście ε jest pomiędzy q1 i q2, więc pozwól q1 jest X i qf jest Y.

Tutaj zbocza wychodzące z q f są do q f dla wejść 0 i 1.

Step 2 -

Teraz skopiujemy wszystkie te krawędzie z q 1 bez zmiany krawędzi z q f i otrzymamy następujące FA -

Step 3 -

Tutaj q 1 jest stanem początkowym, więc q f jest również stanem początkowym.

Więc FA staje się -

Step 4 -

Tutaj q f jest stanem końcowym, więc q 1 jest również stanem końcowym.

Więc FA staje się -