Jak przekonwertować NFA z nakładającymi się cyklami na wyrażenie regularne?

Jeśli dobrze rozumiem, NFA mają taką samą moc ekspresji jak wyrażenia regularne. Często odczytywanie równoważnych wyrażeń regularnych z NFA jest łatwe: przekładasz cykle na gwiazdy, skrzyżowania jako alternatywy i tak dalej. Ale co zrobić w tym przypadku:

^{[ źródło ]}

Nakładające się cykle utrudniają zobaczenie, co akceptuje ten automat (pod względem wyrażeń regularnych). Czy jest jakiś podstęp?

Zamiast „czytać” powinieneś zastosować jedną z kilku kanonicznych metod, aby to zrobić. Zdecydowanie najpiękniejszy, jaki widziałem, to taki, który wyraża automat jako układ równań (zwykłych) języków, które można rozwiązać. Jest to szczególnie miłe, ponieważ wydaje się przynosić bardziej zwięzłe wyrażenia niż inne metody.

Napisałem ten dokument wyjaśniający metodę dla studentów zeszłego lata. Odnosi się bezpośrednio do konkretnego wykładu; wspomniane odniesienie jest typową definicją wyrażeń regularnych. Zawiera dowód Lemmy Ardena (potrzebny wynik); brakuje jednego dla poprawności metody. Jak dowiedziałem się o tym na wykładzie, niestety nie mam odniesienia.

W skrócie: dla każdego stanu utwórz równanie$q_i$

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

gdzie jest zbiorem stanów końcowych, a q i a → q j oznacza przejście z q i na q j oznaczone jako . Jeśli czytasz ∪ jako + lub ∣ (w zależności od definicji wyrażenia regularnego), zobaczysz, że jest to równanie wyrażeń regularnych.$F$$q_i \overset{a}{\to} q_j$$q_i$$q_j$$a$$\cup$$+$$\mid$

Rozwiązywanie go (używając Arden lematu ) daje jedno wyrażenie regularne dla każdego stanu, który opisuje dokładnie te słowa, które mogą być zaakceptowane począwszy q í ; dlatego Q 0 (jeśli q 0 jest stanem początkowym) jest pożądanym wyrażeniem.$Q_i$$q_i$$Q_0$$q_0$

Zastosowanie do danego automatu pozostawia się jako ćwiczenie; pełny przykład znajduje się w powyższym połączonym dokumencie .

^{Zobacz także tutaj, gdzie zamieściłem podobną odpowiedź.}

Gdyby istniał tylko łańcuch stanów bez pętli, czy wiedziałbyś, co robić?

Gdyby istniała prosta pętla bez nakładających się rozgałęzień, czy wiesz, co robić?

(Jeśli odpowiedź brzmi „nie”, najpierw pomyśl o tych przypadkach).

Pomysł polega na stopniowym przekształcaniu automatu w formę, w której można dostrzec te wzorce: łańcuchy, pętle i rozbieżne ścieżki, które zbiegają się na końcu (co prowadzi do naprzemienności). Na każdym etapie transformacji upewnij się, że przekształcony automat nadal rozpoznaje ten sam język.

Należy pamiętać, że jest to non -deterministic automatem. Ten, który opublikowałeś, jest zdeterminowany, ale nie musi tak pozostać, kiedy go przekształcisz.

$q_2$$q_1 \xrightarrow{f} q_2 \xrightarrow{g} q_3$$q_4$$q_2$$q_5$$q_4 \xrightarrow{j} q_5 \xrightarrow{g} q_3$

$q_3,q_4,q_5$$q_3$$q_3$$(hjg)^*$

Sprawdź, które stany są ostateczne. Pomoże to nie martwić się o to na początku i utworzyć jedną dużą pętlę, a następnie powielić części, które kończą się w połowie pętli.

To niekoniecznie jest najbardziej wydajna technika lub ta, która generuje najprostsze wyrażenie regularne, ale jest prosta.