Warianty automatów skończonych

Automaty z $\epsilon$ -przejściami. Niedeterministyczny automat z $\epsilon$ -przejściami $A=(\Sigma,Q,I,\delta,F)$ jest określony jak zwykły automat skończony z tym, że $\delta\subseteq Q\times(\Sigma\cup\{\epsilon\})\times Q$ . Relacja $q\stackrel{w}{\rightarrow}p$ (gdzie $p,q\in Q$ i $w\in\Sigma^{*}$ ) jest określona jak poprzednio, tzn. $q\stackrel{\epsilon}{\rightarrow}q$ i $q\stackrel{va}{\rightarrow}p$ o ile $q\stackrel{v}{\rightarrow}q_{1}$ i $(q_{1},a,p)\in\delta$ z tym, że teraz $a$ może być literą w $\Sigma$ lub $\epsilon$ .

Dowieść, że dla dowolnego automatu z $\epsilon$ -przejściami istnieje zwykły automat skończony, który akceptuje ten sam język.
Automat z wyjściem wg Mealy'ego. Automat Mealy'ego można przedstawić jako deterministyczny automata skończony, powiedzmy $A=(\Sigma,Q,q_{I},\delta,F)$ dany razem z funkcją $\gamma:Q\times\Sigma\to\Delta$ . Intuicyjnie, dany stan $q$ i litera $\sigma\in\Sigma$ determinują nie tylko kolejny stan, powiedzmy $p$ , ale także sygnał wyjściowy (output), $\gamma(q,\sigma)$ . Dokładniej, słowo $w=w_{1}w_{2}\ldots w_{n}$ nad $\Sigma$ , takie, że $\hat{\delta}(q_{I},w_{1}\ldots w_{{i-1}})=p_{i}$ , dla $i=1,\ldots,n$ , wyznacza $n$ -literowe słowo nad alfabetem $\Delta$ ,
$\hat{\gamma}(w)=_{{def}}\gamma(q_{I},w_{1})\gamma(p_{2},w_{2})\ldots\gamma(p_{n},w_{n})$

Powiemy, że automat Mealy'ego redukuje język $L_{1}$ do $L_{2}$ jeśli ( $\forall w$ ) $w\in L_{1}\Leftrightarrow\hat{\gamma}(w)\in L_{2}$ . Skonstruować automat, który redukuje $a^{*}b(a^{*}ba^{*}ba^{*})^{*}$ do $(a^{*}ba^{*}ba^{*})^{*}$ .
Automat z wyjściem wg Moore'a. Automat Moore'a można przedstawić jako deterministyczny automata skończony wraz z funkcją $\gamma:Q\to\Delta$ . Tym razem, słowo $w=w_{1}w_{2}\ldots w_{n}$ wyznacza
$\hat{\gamma}(w)=_{{def}}\gamma(\hat{\delta}(q_{I},w_{1}))\gamma(\hat{\delta}(q_{I},w_{1}w_{2}))\ldots\gamma(\hat{\delta}(q_{I},w_{1}w_{2}\ldots w_{n}))$

Dowieść, że automaty Mealy'ego i Moore'a są równoważne w tym sensie, że dla każdego automatu jednego typu można znale”zć automat drugiego typu realizujący tę samą funkcję $\hat{\gamma}$ .
Automaty dwukierunkowe. Funkcja przejścia deterministycznego automatu dwukierunkowego jest postaci $\delta:Q\times\Sigma\to Q\times\{ L,R\}$ , co interpretujemy, że automat może przesunąć czytnik zarówno w prawo jak i w lewo. Dowieść, że deterministyczne automaty dwukierunkowe mogą być symulowane przez zwykłe automaty skończone
Wskazówka. Znane rozwiązanie oparte na idei ciągów skrzyżowań (ang. crossing sequences) można znale”zć w rozdziale 2.6 książki J.E.Hopcroft, J.D.Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa 1994. Innym, być może prostszym rozwiązaniem – zaproponowanym przez Mikołaja Bojańczyka – jest uwzględnienie w stanie symulującego automatu jednokierunkowego funkcji $h:Q\to Q\cup\{\bot\}$ o następującej interpretacji: jeśli automat (dwukierunkowy) pójdzie w lewo w stanie $q$ , to wróci w stanie $h(q)$ (być może wcale nie wróci, gdy $h(q)=\bot$ ). (Rezultat zachodzi również dla automatów niedeterministycznych.)

Uwaga. W dalszej części wykładu spotkamy się z mocniejszym stwierdzeniem, a mianowicie, że maszyny Turinga pracujące na jednej taśmie w czasie liniowym akceptują jedynie języki regularne.
Dla ustalonego k, rozważmy język nad alfabetem {a,b,c} opisany wyrażeniem
$\left((a+b)^{*}c\right)^{{k-1}}\,(a+b)^{*}a(a+b)^{{k-1}}c\,\left((a+b)^{*}c\right)^{*}$

Intuicyjnie: język składa się z ,,bloków” liter $a,b$ , zakończonych ,,znacznikiem” $c$ , przy czym $k$ -ty (od początku) blok ma tę własność, że jego $k$ -ty symbol od końca jest $a$ .
1. Wykazać, że deterministyczny ,,jednokierunkowy” automat rozpoznający ten język ma $\geq 2^{k}$ stanów.
2. Skonstruować 2-kierunkowy automat o liniowej ( ${\cal O}(k)$ ) liczbie stanów, rozpoznający ten język.
3. (*) Jak wyżej, ale automat ma prawo wykonać tylko jeden nawrót. (Bez zmniejszenia ogólności, możemy założyć, że automat idzie do końca słowa, po czym wraca i kończy obliczenie na początku słowa.)

Informatyka MIMUW

Warianty automatów skończonych