3813100532

4. Ką = (({so? Si) S2-, 53, S4}, {so}> T4), {S4})• Funkcję przejścia Tą opisuje poniższy diagram.

b

Wówczas C(JC4) = {u e S* | u zawiera ciąg aabb}.

5. K₅ = (({so,si,S2,S3,S4,s₅},{so},^5),{s5})- Funkcję przejścia T₅ opisuje poniższy diagram.

Wtedy C(JC5) = {w € S* | długość u jest wielokrotnością liczby 5}.

1.2.3. Równoważność automatów deterministycznych i niedeter-ministycznych

Na każdy automat deterministyczny można spojrzeć jak na automat niedeter-ministyczny. W związku z tym klasa języków rozpoznawanych przez DFA zawiera się w klasie języków rozpoznawanych przez NFA. Okazuje się, że zachodzi również zawieranie w drugą stronę. Dowód tego faktu sprowadza się do pokazania, że każdy niedeterministyczny automat skończony może byś symulowany przez pewien deterministyczny automat skończony, tzn. że dla dowolnego NFA możemy zbudować DFA rozpoznający ten sam język. Oba modele obliczeń są więc równoważne w tym sensie, że klasy języków przez nie rozpoznawanych są takie same. Ta własność jest bardzo użyteczna, bowiem czasem o wiele łatwiej jest opisać NFA akceptujący dany język niż DFA.

Twierdzenie 1.18 ([3]). Dla dowolnego niedeterministycznego automatu skończonego K, = (.4, F) istnieje deterministyczny automat skończony K, taki, że L{JC) = L(JC).

Dowód. ([3]) Niech K — (A,F) będzie niedeterministycznym automatem skończonym, A — (S,I,T). Definiujemy:

JC = {A,F'),    A=(S',{I},T) gdzie :

15