-
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\).
- Wykazać, że deterministyczny ,,jednokierunkowy” automat rozpoznający ten język ma \(\geq 2^{k}\) stanów.
- Skonstruować 2-kierunkowy automat o liniowej (\({\cal O}(k)\)) liczbie stanów, rozpoznający ten język.
- (*) 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.)