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

Ć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^2{a}^{4l}$, gdzie $l\in \mathbb{\mathbb{N}}$, zatem szukane $k$ ma postać $k=4l+2,l\in \mathbb{\mathbb{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^{n}bx{y}_1{y}_2...y_k{b}^l$, $n,k,l\ge 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\ge 0$, $i=1,\dots ,k$.

Ćwiczenie 3

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

Rozwiązanie

$[1]=\{a^n:n\ge 0\}$
$[b]=\{a^{m}b{y}_1{y}_2...y_p$ $:$ $y_i=b^{s_i}a\text{ lub }{y}_i=a{b}^{t_i}a,m,p,t_i\ge 0,s_i>0,i=1,\dots ,p\}$
$[ba]=\{a^{n}bx(b^{m_1}a{y}_1)...(b^{m_p}a{y}_p)b^r$ $:$ $n,m_i,p,r\ge 0,x,y_i\in \{a,b\},i=1,\dots ,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

Rysunek 4

Ćwiczenie 5

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

Rysunek 5

Rozwiązanie

Tak.

Ćwiczenie 6

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

• $\mathrm{\forall }i\in \{1,2\}{\tau }_{{𝒜}}(b)(s_i)=s_{3-i}$ ($i=1,2$),

• $\mathrm{\forall }s\in S{\tau }_{{𝒜}}(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 ${𝒜}$ zadanego grafem

Rysunek 6

Jakie języki akceptują automaty ${{𝒜}}_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({𝒜})=\{{\tau }_{{𝒜}}(1),{\tau }_{{𝒜}}(a),{\tau }_{{𝒜}}(b)\}=\{{\tau }_{{𝒜}}(a),{\tau }_{{𝒜}}(b){\}}^{*}$
$L({{𝒜}}_i)=\{w\in \{a,b\}:{\mathrm{\#}}_{a}w-{\mathrm{\#}}_{b}w=imod3\}$.

Ćwiczenie 8

Rozważmy automat synchronizujący ${𝒜}=(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 ${𝒜}$ jego najkrótsze słowo synchronizujące nazywamy minimalnym słowem synchronizującym, a jego długość oznaczamy przez $m({𝒜})$. Niech $SYN(n)$ oznacza zbiór wszystkich $n$-stanowych automatów synchronizujących i tylko takich.

Udowodnij, że

$\mathrm{\forall }{𝒜}\in SYN(n)m({𝒜})\le n^3$.

Wskazówka

Rozważ długości słów synchronizujących pary stanów automatu ${𝒜}$, czyli słów $w_{pq}$ takich, że $|\{f(p,w_{pq}),f(q,w_{pq})\}|=1$. Wykorzystaj fakt, że słowo synchronizujące dla ${𝒜}$ 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_1{w}_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_i{w}_{j+1}...w_t$. Możemy więc założyć, że dla $i=j$ zachodzi $f(\{p,q\},w_1...w_i)=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 $(\genfrac{}{}{0ex}{}{n}{2})$ dwuelementowych podzbiorów $n$-elementowego zbioru stanów, zatem słowo $w_{pq}$ może mieć długość co najwyżej $(\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{n}{2})\le 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 ${𝒜}$ akceptujący język

$L({𝒜})=\{w\in \{a,b\}:{\mathrm{\#}}_{a}w={\mathrm{\#}}_{b}wmod2\}$.