Automaty skończone

Deterministyczne automaty skończone

Deterministyczny automat skończony (DFA) opisany jest pięcioelementowym tuplem: (Q,Σ,δ,q0,F)(Q, χigma, χdelta, q_0, F)(Q,Σ,δ,q0,F).

QQQ = skończony zbiór stanów

Σ \SigmaΣ = skończony, niepusty alfabet wejściowy

δdeltaδ = szereg funkcji przejścia

q0q_0q0 = stan początkowy

FFF = zbiór stanów akceptujących

Dla każdego symbolu wejściowego w ΣSigmaΣ musi istnieć dokładnie jedna funkcja przejścia z każdego stanu.

DFA mogą być reprezentowane przez diagramy tej postaci:

Tutaj znajduje się diagram DFA opisujący kilka prostych ruchów, które może wykonać postać w grze wideo: stanie, bieg i skok. Przyciski, których gracz może użyć do kontrolowania tej konkretnej postaci, to „Up”, „A” lub gracz może nie nacisnąć żadnego przycisku.

Używając diagramu stanu dla postaci z gry wideo powyżej, opisz jak gracz może kontrolować swoją postać, aby przejść od stania do biegania i skakania.

Pokaż odpowiedź

W stanie stojącym gracz może nic nie naciskać i pozostać w stanie stojącym, następnie, aby przejść do stanu biegu, użytkownik musi nacisnąć przycisk „W górę”. W stanie biegania, użytkownik może nadal sprawić, że jego postać będzie biegła, naciskając przycisk „W górę”, a następnie, aby przejść do stanu skoku, użytkownik musi nacisnąć „A.”.

Narysuj diagram dla DFA, który rozpoznaje następujący język: Język wszystkich ciągów, które kończą się cyfrą 1.

Pokaż odpowiedź

Nondeterministyczne automaty skończone

QQQ = skończony zbiór stanów

ΣSigmaΣ = skończony, niepusty alfabet wejściowy

δdeltaδ = szereg funkcji przejścia

q0q_0q0 = stan początkowy

FFF = zbiór stanów akceptujących

W przeciwieństwie do DFA, NDFA nie muszą mieć funkcji przejścia dla każdego symbolu w ΣSigmaΣ, a w tym samym stanie może być wiele funkcji przejścia dla tego samego symbolu. Dodatkowo, NDFA mogą używać przejść zerowych, które są wskazywane przez ϵepsilonϵ. Przejścia zerowe pozwalają maszynie przeskakiwać z jednego stanu do drugiego bez konieczności odczytywania symbolu.

An NDFA akceptuje łańcuch xxx jeśli istnieje ścieżka, która jest zgodna z tym łańcuchem i kończy się stanem akceptacji.

NDFA mogą być reprezentowane przez diagramy tej postaci:

źródło

Opisz język, który rozpoznaje powyższa NDFA.

Pokaż odpowiedź

Powyższy NDFA rozpoznaje ciągi znaków kończące się na „10” i ciągi znaków kończące się na „01”.

Stan aaa jest stanem początkowym, a stamtąd możemy utworzyć ciąg z dowolną liczbą 1 i 0 w dowolnej kolejności, a następnie przenieść się do stanu bbb lub stanu eee, lub możemy natychmiast przenieść się do stanu bbb lub stanu eee. W każdym razie NDFA zaakceptuje tylko taki ciąg, który osiągnie stan ddd lub ggg. Aby osiągnąć stan ddd lub ggg, łańcuch musi kończyć się znakiem „01” (dla stanu ddd) lub „10” (dla stanu ggg).

Na przykład, następujące ciągi są rozpoznawane przez NDFA.

• 00000000010
• 10
• 01
• 1111101