Języki, automaty i obliczenia/Ćwiczenia 3: Automat skończenie stanowy

From Studia Informatyczne

ĆWICZENIA 3

Ćwiczenie 1

Dla jakich k słowo a^k należy do języka akceptowanego przez automat z rysunku 1.



Rysunek 1

Rozwiązanie

Słowa o żądanej własności to słowa postaci a^2a^{4l}, gdzie l \in \mathds{N}, zatem szukane k ma postać k=4l+2,\ l  \in \mathds{N}.

Ćwiczenie 2

Opisz słownie język L akceptowany przez poniższy automat.



Rysunek 2

Rozwiązanie

Język L składa się ze słów postaci a^nbxy_1y_2...y_kb^l, n, k, l \geq 0, gdzie {x} jest literą {a} lub {b}, a każde {y_i} ma postać b^{m_i}a^2 lub b^{m_i}ab, gdzie m_i \geq 0, i=1,...,k.

Ćwiczenie 3

Wyznacz prawą kongruencję automatową dla trzystanowego automatu z rysunku 2 (patrz ćwiczenie 2).

Rozwiązanie

[1]=\{a^n : n \geq 0\}
[b]= \{a^mby_1y_2...y_p : \ y_i = b^{s_i}a \mbox{ lub } y_i = ab^{t_i}a,\ m,p,t_i \geq 0, s_i >0, i=1,...,p\}
[ba]=\{a^nbx(b^{m_1}ay_1)...(b^{m_p}ay_p)b^r : n,m_i,p,r \geq 0 ,\ x, y_i \in \{a,b\},\ i=1,...,p \}

Ćwiczenie 4

Uzupełnij poniższy rysunek w ten sposób, by uzyskany 4-stanowy automat nie akceptował żadnego słowa nad alfabetem \{a, b\}, w którym dwie litery {b} występują obok siebie.



Rysunek 3


Rozwiązanie

<flash>file=ja-lekcja03-c-rys5.swf|width=250|height=250</flash>

Rysunek 4

Ćwiczenie 5

Sprawdź, czy następujące automaty są równoważne.



Rysunek 5


Rozwiązanie

Tak.

Ćwiczenie 6

Wyznacz automat \mathcal{A}=(S=\{s_1,s_2\}, f) (nad alfabetem \{a, b\}), którego reprezentacja \tau_{\mathcal{A}} spełnia następujące warunki:

  • \forall i \in \{1,2\}\ \tau_{\mathcal{A}}(b)(s_i)=s_{3-i} (i=1,2),
  • \forall s \in S\ \tau_{\mathcal{A}}(ab)(s)=s_1

Czy automat ten jest wyznaczony jednoznacznie?

Rozwiązanie

Z pierwszego warunku otrzymujemy f(s_1,b)=s_2, f(s_2,b)=s_1. Z drugiego warunku mamy f(s_1,ab)=s_1 oraz f(s_2,ab)=s_1. Ponieważ f(s_1,ab)=f(f(s_1,a),b)=s_1, a pod wpływem b do stanu s_1 możemy przejść tylko ze stanu s_2, zatem f(s_1,a)=s_2. Analogicznie: f(s_2,ab)=f(f(s_2,a),b))=s_2. Ponieważ pod wpływem b do stanu s_2 można przejść tylko ze stanu s_1, zatem musi być f(s_2, a)=s_1. Obliczyliśmy więc {f} dla wszystkich stanów i wszystkich liter alfabetu. Funkcja przejścia wyznaczona jest jednoznacznie.

Ćwiczenie 7

Określ monoid przejść automatu \mathcal{A} zadanego grafem



Rysunek 6

Jakie języki akceptują automaty \mathcal{A}_i dla i=0,1,2, zadane grafem z rysunku 6, jeśli stanem początkowym jest s_0, a zbiór stanów końcowych T_i=\{s_i\}?


Rozwiązanie

M(\mathcal{A})=\{\tau_{\mathcal{A}}(1),  \tau_{\mathcal{A}}(a), \tau_{\mathcal{A}}(b)\}=  \{ \tau_{\mathcal{A}}(a), \tau_{\mathcal{A}}(b)\}^*
L(\mathcal{A}_i) = \{ w \in \{a,b\} :  \#_aw- \#_bw = i\; mod\; 3\}.

Ćwiczenie 8

Rozważmy automat synchronizujący \mathcal{A}=(S, A, f), gdzie S jest {n}-elementowym zbiorem stanów, a A dowolnym, skończonym alfabetem (definicja automatu synchronizującego podana jest w wykładzie nr 3). Dla automatu synchronizującego \mathcal{A} jego najkrótsze słowo synchronizujące nazywamy minimalnym słowem synchronizującym, a jego długość oznaczamy przez m(\mathcal{A}). Niech SYN(n) oznacza zbiór wszystkich {n}-stanowych automatów synchronizujących i tylko takich.

Udowodnij, że

\forall \mathcal{A} \in SYN(n)\  m(\mathcal{A}) \leq n^3.

Wskazówka

Rozważ długości słów synchronizujących pary stanów automatu \mathcal{A}, czyli słów w_{pq} takich, że |\{f(p,w_{pq}), f(q,w_{pq})\}|=1. Wykorzystaj fakt, że słowo synchronizujące dla \mathcal{A} ma być minimalne.

Rozwiązanie

Jeśli automat jest synchronizujący, to dla każdych dwóch stanów {p} i {q} istnieje słowo w_{pq}, które synchronizuje te dwa stany, tzn. f(p,w_{pq})=f(q,w_{pq}). Wybierzmy dwa dowolne stany {p},{q} ze zbioru stanów automatu. Jak długie może być słowo w_{pq}=w_1w_2...w_t synchronizujące te dwa stany? Kolejne litery tego słowa mogą przeprowadzać zbiór stanów \{p,q\} w zbiory innych dwuelementowych stanów. Zauważmy, że jeśli dla pewnych i<j zachodzi f(\{p,q\},w_1...w_i)=f(\{p,q\},w_1...w_j), to jako w_{pq} możemy wybrać krótsze słowo, w_{pq}=w_1...w_iw_{j+1}...w_t. Możemy więc założyć, że dla i \not = j zachodzi f(\{p,q\},w_1...w_i) \not = f(\{p,q\},w_1...w_j), czyli wszystkie dwuelementowe podzbiory powstałe w wyniku przekształceń zbioru \{p,q\} przez kolejne litery słowa w_{pq} są parami różne. Ponadto, ostatni zbiór, f \{p,q\},w_1...w_t), jest jednoelementowy, gdyż założyliśmy, że w_{pq} ma synchronizować stany {p} i {q}.

Ponieważ istnieje \binom{n}{2} dwuelementowych podzbiorów {n}-elementowego zbioru stanów, zatem słowo w_{pq} może mieć długość co najwyżej \binom{n}{2}. Po przekształceniu zbioru {S} stanów przez słowo w_{pq} znajdziemy się w co najwyżej {n-1}-elementowym zbiorze S_1 \subset S. Z tego zbioru znów wybieramy dwa stany {p,q}, szukamy dla nich słowa synchronizującego i przekształcamy przez to słowo zbiór S_1 otrzymując co najwyżej n-2-elementowy zbiór S_2. W najgorszym przypadku powyższą procedurę będziemy musieli powtórzyć {n-1} razy aby zsynchronizować wszystkie stany ze zbioru {S} do jednego stanu. Słowem synchronizującym będzie konkatenacja słów w_{pq} synchronizujących pary stanów w poszczególnych krokach.

Długość tego słowa będzie nie większa niż (n-1) \cdot \binom{n}{2} \leq n^3, co należało dowieść.

ZADANIA DOMOWE

Ćwiczenie 9

Sprawdź, które z poniższych słów należą do języka akceptowanego przez automat z ćwiczenia 1 (patrz ćwiczenie 1.)

(1) abbbab,
(2) aabbaa,
(3) a^6,
(4) ababaa,
(5) ba.

Ćwiczenie 10

Sprawdź, czy następujące automaty są równoważne.



Rysunek 7


Ćwiczenie 11

Wyznacz monoid przejść następującego automatu:



Rysunek 8


Ćwiczenie 12

Określ automat \mathcal{A} akceptujący język

L(\mathcal{A}) = \{ w \in \{a,b\} :  \#_aw =\#_bw \; mod\; 2\}.