✖

Uogólniony niedeterministyczny automat skończony

Kapitoly: Wyrażenia regularne, Konwersja wyrażenia regularnego na automat, Uogólniona NKA, Konwersja automatu na wyrażenie regularne

Uogólniony niedeterministyczny automat skończony, w skrócie ZNKA, jest niedeterministycznym automatem, który może mieć nie tylko symbole z języka w przejściach, ale może mieć tam wyrażenie regularne.

Definicja

Będziemy potrzebować ZNKA podczas algorytmu konwersji skończonego autom atu na wyrażenie regularne. ZNKA jest więc NKA, która ma przejścia zdefiniowane przez wyrażenia regularne. Przykład takiej ZNKA:

Widzimy, że na przykład przejście ze stanu q2 prowadzi do stanu q3 i jest oznaczone wyrażeniem regularnym $a^\ast b$. Inne wymagania dla ZNKA:

  • Stan początkowy q0 musi mieć przejście do wszystkich innych stanów. Na rysunku widzimy, że ze stanu q0 istnieją przejścia do wszystkich innych stanów.
  • W ZNKA istnieje tylko jeden stan końcowy, a wszystkie inne stany mają przejście do tego stanu. Jak widać na rysunku, wszystkie stany mają strzałkę wskazującą na qf.
  • Stan początkowy nie może być taki sam jak stan końcowy. Zatem ZNKA może mieć co najmniej dwa stany.
  • Wszystkie inne stany, z wyjątkiem początkowego i końcowego, muszą mieć przejścia do wszystkich innych stanów z wyjątkiem początkowego i końcowego. W tym pętle (przejście ze stanu qi do stanu qi).

Konwersja normalnej NKA do ZNKA

Jeśli mamy NKA, konwersja do ZNKA jest prosta.

  1. Tworzymy nowy stan początkowy qs i tworzymy przejście epsilon do oryginalnego stanu początkowego.
  2. Tworzymy nowy stan końcowy qf i wykonujemy przejścia epsilon ze wszystkich oryginalnych stanów końcowych do stanu qf. Z oryginalnych stanów końcowych tworzymy stany normalne.
  3. Jeśli gdzieś istnieje wiele przejść (np. jeśli przejdziemy ze stanu q1 do stanu q2 przez symbol 0 i przez symbol 1), łączymy te reguły w jedno wyrażenie regularne i łączymy wszystkie oryginalne symbole za pomocą operatora unii (tj. zaznaczamy strzałkę wyrażeniem regularnym 0|1).
  4. Jeśli w automacie brakuje przejścia, które z definicji powinno tam być, tworzymy je i oznaczamy wyrażeniem regularnym ∅. Nie zmienia to języka akceptowanego przez automat, ponieważ takie przejście nigdy nie jest wykonywane.

Możemy użyć tego automatu do konwersji automatu na wyrażenie regularne.