Przekształcenie wyrażenia regularnego w automat
Pokażemy, jak przekształcić dowolne wyrażenie regularne w niedeterministyczny automat skończony.
Przykład
Zanim opiszemy sam algorytm, pokażemy na przykładzie, o co nam właściwie chodzi. Weźmy takie wyrażenie regularne: a(b|c)x∗. Słownie opisalibyśmy język, który generuje to wyrażenie regularne, jako słowa, które zaczynają się literą „a”, po niej następuje litera „b” albo „c”, a potem dowolna liczba liter „x”. Potrafilibyśmy zbudować automat, który akceptowałby ten język? Pewnie, spójrz:
Ten automat oczywiście akceptuje ten sam język. Nasuwa się więc pytanie, czy dla każdego wyrażenia regularnego istnieje automat, który akceptuje dany język. No cóż, tak.
Algorytm przekształcenia wyrażenia regularnego w automat
Zakładamy, że na wejściu mamy wyrażenie regularne R. Z poprzedniej części o wyrażeniach regularnych wiemy, że wyrażenie regularne może mieć łącznie sześć różnych postaci. Rozróżnimy więc sześć różnych przypadków:
-
R = a dla pewnego symbolu a ∈ Σ. Czyli wyrażenie regularne to tylko jeden symbol z alfabetu Σ, nad którym pracujemy. Automat, który akceptowałby jeden symbol a, wyglądałby tak:
-
R = ϵ, słowo puste. Automat, który akceptowałby słowo puste, wyglądałby tak:
-
R = ∅, wyrażenie regularne, które generuje język pusty. Automat, który rozpoznaje taki język, wygląda tak:
-
R = R1 ∪ R2, gdzie R1, R2 są wyrażeniami regularnymi. Wiemy już, że suma języków regularnych jest znowu językiem regularnym i że potrafimy zbudować automat, który taki język akceptuje. Innymi słowy, zakładamy, że mamy automaty, które rozpoznają języki generowane przez wyrażenia R1 i R2, i za ich pomocą zbudujemy automat, który akceptuje język generowany przez wyrażenie R1 ∪ R2. Przykład: jeśli R1 = a i R2 = ϵ, to według tej konstrukcji dostaniemy taki automat:
-
R = R1 ∘ R2, gdzie R1, R2 są wyrażeniami regularnymi. Podobnie jak w poprzednim punkcie. Konkatenacja języków regularnych jest językiem regularnym, więc potrafimy zbudować automat, który będzie taki język akceptował. Jeśli więc R1 = a, R2 = b, to konkatenacja wyglądałaby tak:
-
, gdzie R1 jest wyrażeniem regularnym. Znowu wiemy, że domknięcie Kleene’ego języka regularnego jest językiem regularnym. Jeśli więc R = a∗, to automat wyglądałby tak:
Stosując po kolei te punkty, przekształcimy całe wyrażenie regularne w automat skończony.
Pełny przykład
Spróbujemy przekształcić wyrażenie regularne (a|bc)∗. Po kolei dostaniemy takie automaty:
Ten wynikowy automat akceptuje język, który generuje wyrażenie regularne (a|bc)∗. Oczywiście automat jest strasznie skomplikowany i na pewno istnieje dużo prostszy automat, który akceptuje ten sam język. Możemy użyć algorytmu przekształcenia NFA w DFA, a następnie przeprowadzić minimalizację automatu.
Źródła
Rozdziały: Wyrażenia regularne, Wyrażenie regularne na automat, Uogólniony NFA, Automat na wyrażenie regularne