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ę -