3813100531

1.2.2. Języki rozpoznawane przez automaty skończone

Niech K. = {A, F) będzie automatem skończonym. Rozważmy zbiór wszystkich skończonych słów akceptowanych przez fC. Niech

jC(IC) := {u € £* | K. akceptuje u}.

Definicja 1.16. Mówimy, że język jC jest rozpoznawany przez automat skończony, jeśli istnieje automat skończony K taki, że C = C(K).

Przykład 1.17.

Oto przykłady automatów skończonych nad alfabetem £ = {a,b} oraz języków przez nie rozpoznawanych.

1. K\ = (({so>si}) (so},Ti), {si}). Funkcję przejścia Ti opisuje poniższy diagram.

a, b

Wtedy C(Ki) = £*.

2. Ki = (({sO)Si)52},{so}ł^2)₅{52})- Funkcję przejścia T2 opisuje poniższy diagram.

a, b

Wówczas £(/C2) = {u G S* | u zaczyna się symbolem a i kończy symbolem 6}.

3. K3 = (({so) si, S2}, {so}>T3), {si}). Funkcję przejścia T3 opisuje poniższy diagram :

14