✖

Przekształcenie wyrażenia regularnego w automat

Kapitoly: Wyrażenia regularne, Wyrażenie regularne na automat, Uogólniony NFA, Automat na wyrażenie regularne

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^\ast$. 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:

  1. R = a dla pewnego symbolu $a\in\Sigma$. Czyli wyrażenie regularne to tylko jeden symbol z alfabetu $\Sigma$, nad którym pracujemy. Automat, który akceptowałby jeden symbol a, wyglądałby tak:

  2. R = ε, słowo puste. Automat, który akceptowałby słowo puste, wyglądałby tak:

  3. R = ∅, wyrażenie regularne, które generuje język pusty. Automat, który rozpoznaje taki język, wygląda tak:

  4. 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:

  5. $R=R_1\circ R_2$, 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:

  6. $R=(R_1^\ast)$, 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^\ast$, 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)^\ast$. Po kolei dostaniemy takie automaty:

Ten wynikowy automat akceptuje język, który generuje wyrażenie regularne $(a|bc)^\ast$. 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