✖

Uogólniony niedeterministyczny automat skończony

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

Uogólniony niedeterministyczny automat skończony, w skrócie GNFA (od ang. generalized nondeterministic finite automaton), to automat niedeterministyczny, który na przejściach nie musi mieć tylko symboli z alfabetu, ale może tam mieć wyrażenie regularne.

Definicja

GNFA będzie nam potrzebny w algorytmie przekształcenia automatu skończonego w wyrażenie regularne. GNFA to więc NFA, który ma przejścia opisane wyrażeniami regularnymi. Przykład takiego GNFA:

Widzimy, że np. ze stanu q2 prowadzi przejście do stanu qf i jest opisane wyrażeniem regularnym $a^\ast b$. Pozostałe wymagania wobec GNFA:

  • Stan początkowy q0 musi mieć przejście do wszystkich pozostałych stanów. Na rysunku widzimy, że ze stanu q0 prowadzą przejścia do wszystkich pozostałych stanów.
  • W GNFA istnieje tylko jeden stan akceptujący i wszystkie pozostałe stany mają do tego stanu przejście. Jak widać na rysunku, ze wszystkich stanów prowadzi strzałka do qf.
  • Stan początkowy nie może być tym samym stanem co stan akceptujący. GNFA ma więc co najmniej dwa stany.
  • Wszystkie pozostałe stany, oprócz początkowego i akceptującego, muszą mieć przejścia do wszystkich pozostałych stanów oprócz początkowego i akceptującego. Łącznie z pętlami (przejście ze stanu qi do stanu qi).

Przekształcenie zwykłego NFA w GNFA

Jeśli mamy jakiś NFA, przekształcenie go w GNFA jest proste.

  1. Utworzymy nowy stan początkowy qs i utworzymy z niego epsilon-przejście do pierwotnego stanu początkowego.
  2. Utworzymy nowy stan akceptujący qf i ze wszystkich pierwotnych stanów akceptujących poprowadzimy epsilon-przejścia do stanu qf. Z pierwotnych stanów akceptujących zrobimy zwykłe stany.
  3. Jeśli gdzieś istnieje przejście wielokrotne (czyli jeśli ze stanu q1 dostaniemy się do stanu q2 zarówno przez symbol 0, jak i przez symbol 1), to te przejścia połączymy w jedno wyrażenie regularne i wszystkie pierwotne symbole połączymy operatorem sumy (czyli opiszemy strzałkę wyrażeniem regularnym 0|1).
  4. Jeśli w automacie brakuje jakiegoś przejścia, które według definicji powinno tam być, utworzymy je i opiszemy wyrażeniem regularnym ∅. Nie zmienimy tym języka, który automat akceptuje, bo takie przejście nigdy się nie wykona.

Ten automat możemy wykorzystać do przekształcenia automatu w wyrażenie regularne.