Do tej części zadań może podejść Czytelnik bez żadnej znajomości teorii automatów.
Czy Barman noże wygrać startując z nieznanej konfiguracji początkowej, a jeśli tak, to w jakiej liczbie ruchów?
Czy graliby Państwo o pieniądze z Barmanem ? A gdyby zamiast kwadratu były 3 szklanki ustawione w trójkąt lub 5 w pięciokąt ?
Jeśli skończony zbiór \(C\) nie jest kodem, oszacować z góry długość najkrótszego słowa, które o tym świadczy (tzn. dopuszcza dwie różne faktoryzacje).
Jeśli \(|\Sigma|<\infty\) to dla każdego \(X\subseteq\Sigma^{*}\) zbiór jego słów minimalnych w sensie \(\preceq\) jest skończny.
Wskazówka. Przypuśćmy, że teza jest fałszywa. Wtedy istnieje w \(\Sigma^*\) nieskończony ciąg słów \(x_{1},x_{2},..\) taki że \(i < j\ \rightarrow\ not\ (x_{i}\preceq x_{j})\) (ale może być \(x_{j}\preceq x_{i}\)). Wybierzmy taki ”minimalny” ciąg w sensie długości, tzn. \(|x_{1}|\) minimalne, jeśli \(x_{1}\) ustalone to \(|x_{2}|\) minimalne itd. Wybierzmy podciąg nieskończony \(x_{{i_{1}}},x_{{i_{2}}}..\) wszystkich słów z tego ciągu zaczynających się na pewną taką samą literę \(a\). Usuńmy tę literę z początku każdego z tych słów otrzymując ciąg \(x^{{\prime}}_{{i_{1}}},x^{{\prime}}_{{i_{2}}}..\). Wtedy ciąg \(x_{1},x_{2},\ldots,x_{{i_{1}-1}},x^{{\prime}}_{{i_{1}}},x^{{\prime}}_{{i_{2}}},x^{{\prime}}_{{i_{3}}}\ldots\) spełnia te same warunki co początkowy ciąg i jest ”mniejszy”, sprzeczność.
Wskazówka. Skorzystaj z lematu Higmana (poprzednie zadanie)..
Wskazówka. Skorzystać z poprzedniego zadania.
Jak najkrócej reprezentować zbiór słów, w których te liczby są tej samej parzystości?
Uwaga. Fakt analogiczny do ?? można udowodnić dla dowolnej reprezentacji, a zatem zbiór semi–liniowy jest regularny w reprezentacji o podstawie \(k\), dla \(k\geq 1\). W przeciwnym kierunku wiadomo, że jeśli zbiór jest regularny w reprezentacjach o względnie pierwszych podstawach \(p\) i \(q\), to jest semi–liniowy — jest to wniosek z głębokiego Twierdzenia Cobhama.
Jeśli \(L\) jest regularny, to
(*) Istnieje stała \(n_{0}\), że dla każdych słów \(v,w,u\) takich że \(|w|\geq n_{0}\) i \(vwu\in L\), istnieją \(x,y,z\) takie, że \(w=xyz\), \(0< |y|\leq n_{0}\), oraz \(\forall n\in{\bf N},\, vxy^{n}zu\in L\).
Podać przykład języka \(L\), który spełnia (*), choć nie jest regularny.
Wskazówka. \(\sum _{p}\underbrace{cb^{*}cb^{*}\ldots cb^{*}}_{p}+(b+c)^{*}cc(b+c)^{*}\), gdzie \(p\) przebiega liczby pierwsze.
\(\{ w\in(a+b)^{*}:\ \# _{a}(u)>2009\cdot\# _{b}(u)\textrm{\quad dla ka"rdego niepustego prefiksu $u$ s"lowa $w$}\}\)\(u\) słowa \(w\)
\(\# _{s}\) oznacza liczbę wystąpień symbolu \(s\) w słowie.
\(x\ =\ z\;\bar{z}^{R}\) lub \(x\ =\ z\; s\;\bar{z}^{R}\),
gdzie \(\bar{z}\) oznacza negację (logiczną) elementów w \(z\). Np. 0010011, 0011 są antypalindromami, a słowo puste i pojedyńczy symbol nie są. Niech \(L\) będzie zbiorem słów binarnych nie zawierających jako podsłowa antypalindromu o długości większej niż 3 zaczynającego się od zera. Czy \(L\) jest regularny ?
\(\displaystyle X^{{-1}}L = \{ w:\,(\exists v\in X)\, vw\in L\}\)
\(\displaystyle LX^{{-1}} = \{ w:\,(\exists u\in X)\, wu\in L\}\)
są regularne.
Uwaga. Lustrzane odbicie \(w^{R}\) słowa \(w\) możemy w ścisły sposób zdefiniować rekurencyjnie: \(\epsilon^{R}=\epsilon\) i \((w\sigma)^{R}=\sigma w^{R}\), dla \(w\in\Sigma^{*}\), \(\sigma\in\Sigma\).
\(\mbox{Cycle}(L)=\{ vu\,:\, uv\in L\}\)
Czy z faktu, że język \(\mbox{ Cycle}(L)=\{ vu\,:\, uv\in L\}\) jest regularny, można wnioskować, że język \(L\) jest regularny?
\(\{ w\,:\, w\in L\wedge\mbox{ spośróod słów o dlugości $|w|$, $w$ jest najmniejsze w porządku leksykograficznym}\}\)\(|w|\), \(w\) jest najmniejsze w porządku leksykograficznym
\(\mbox{bin}(w)=w_{1}\frac{1}{2}+w_{2}\frac{1}{2^{{2}}}+\ldots+w_{k}\frac{1}{2^{{k}}}\)
Dla liczby rzeczywistej \(r\in[0,1]\), niech
\(L_{r}=\{ w\,:\,\mbox{bin}(w)\leq r\}\)
Dowieść, że język \(L_{r}\) jest regularny wtedy i tylko wtedy, gdy liczba \(r\) jest wymierna.
\(F_{1}=F_{2}=1\)
\(F_{{n+2}}=F_{n}+F_{{n+1}}\)
\(\{ w\,:\, w^{{|w|}}\in L\}.\)
\(L\,=\,\{ i_{1}i_{2}\ldots i_{k}:L_{{i_{1}}}L_{{i_{2}}}\ldots L_{{i_{k}}}\subseteq L\}\)
Czy język \((\{ ww^{R}:w\in(0+1)^{*}\})^{*}\) jest regularny?
Oznaczmy przez \(\mathit{Ile}(w,x)\) liczbę wystąpień słowa \(w\) jako podsłowo \(x\) (wystąpienia nie muszą być rozłączne). Czy następujący język nad alfabetem \(\{ a,b\}\) jest regularny? Jeśli tak, to podać wyrażenie regularne. Jeśli nie, to udowodnić, że nie jest.
są językami regularnymi, a język
może nie być regularny.
\(d(u,w)=|\{ i:w_{i}\neq v_{i}\}|.\)
Udowodnić, że dla dowolnego języka regularnego \(L\) i stałej \(K\), następujący język jest również regularny:
\(\{\ w\ :\ (\exists\ u\in L)\ |u|=|w|\ \textrm{oraz}\ d(u,w)\le K\ \}\)
Przeplotem słów \(w\) i \(v\) nazwiemy dowolne słowo długości \(|w|+|v|\), które można rozbić na rozłączne podciągi \(w\) i \(v\). Na przykład, przeplotami słów \(ab\) i \(acb\) są słowa \(abacb\), \(aabcb\), \(acabb\), \(acbab\), \(aacbb\). Przeplotem języków \(L\) i \(M\) jest zbiór wszystkich możliwych przeplotów słów \(w\in L\), \(v\in M\). Język ten oznaczamy \(L\parallel M\).
Dowieść, że jeśli \(L\) i \(M\) są językami regularnymi, to \(L\parallel M\) jest również regularny.
Udowodnić, że skończony język \(L_{n}\ =\ \{ w(\alpha)\ :\ \alpha\in X_{n}\}\) jest akceptowany przez dwukierunkowy det. automat skończony mający \(O(n)\) stanów, ale jednokierunkowy automat deterministyczny musi mieć wykładniczą liczbę stanów.
słowa \(abbababa\) (dla przejrzystości rysunków pominąć stan ,,śmietnik”).
Ile stanów maja analogiczne automaty dla \(w_{n}=ab(ba)^{n}\) (licząc stan ,,śmietnik”) ?
(W szczególności słowo puste należy do obu języków, a słowo 111 do żadnego z nich.)
\(2^{{n-1}}\) stanów,
\(2^{n}\) stanów.
Na powyższych rysunkach \(n=7\), stan początkowy jest wskazany przez \(\Rightarrow\), a stan akceptujący jest oznaczony przez \(\bullet\).
Uwaga. Właność słów rozpoznawaną przez automat z punktu można łatwo opisać w języku polskim, w przypadku punktu jest to trudniejsze.
Wskazówka. Jako stany minimalnego automatu weżmy ciągi binarne długości 7 zawierające dokłądnie 4 jedynki,
plus stan typu śmietnik.
Naturalny automat pamięta historie (ciąg binarny) ostatnich siedmiu dni.
Każdy taki ciąg jest równoważny ciągowi dopełnionemu: zamieniamy kolejne zera od lewej na jedynke tak aby w sumie
były 4 jedynki.
Zatem ostatecznie automat ma tyle stanów ile jest ciągów binarnych długości 7 mających 4 jedynki, plus stan smietnik.
W sumie 35+1=36.
— Każdy napój kosztuje 1 złoty.
— W chwili początkowej automat nie zawiera żadnych monet.
— Automat przyjmuje monety: 1 złoty lub 1 euro; w tym ostatnim przypadku wydaje 3 złote reszty po warunkiem, oczywiście, że ma dostateczną ilość monet jednozłotowych (zakładamy, że €1 = 4 zł).
— Jeśli automat nie jest w stanie wydać reszty — sygnalizuje błąd.
— Jeśli po wrzuceniu monety i ewentualnym wydaniu reszty wartość wszystkich monet zgromadzonych w automacie osiągnie równowartość 8 zł, wszystkie monety są wyjmowane (reset).
Historią działania jest ciąg wrzuconych monet (złoty lub euro). Historia jest udana, jeśli w trakcie jej realizacji ani razu nie wystąpił błąd.
Skonstruować minimalny automat deterministyczny rozpoznajacy zbiór wszystkich udanych historii.
Prof. J. Brzozowski zauważył, następującą własność
\((*)\) jeśli \(A\) jest deterministyczny to \(det(A^{R})\) jest minimalnym automatem deterministycznym dla języka \(L(A)^{R}\).
Udowodnić własność \((*)\).
Wskazówka. Wykazać, że dla każdej liczby \(k\) istnieje co najwyżej jedno nietrywialne przejście wsteczne, takie, że \(|va|-|u|=k\).
Dla danego słowa \(w\) o długości \(|w|=n\) skonstruować automat deterministyczny o \(\leq 2n+1\) stanach rozpoznający dokładnie zbiór sufiksów słowa \(w\).
Wskazówka. Jako stany automatu można wziąć zbiory pozycji \(S_{x}\) (\(S_{x}\subseteq\{ 0,1,\ldots,n\}\)) kończących wystąpienie \(x\) jako podsłowa słowa \(w\). Oszacowanie na liczbę stanów wynika ze spostrzeżenia, że różne zbiory \(S_{x}\), \(S_{y}\) są albo w relacji inkluzji albo rozłączne, a zatem, ze względu na inkluzję, tworzą drzewo o nie więcej niż \(n\) liściach.
Powyższy automat zawiera stan typu ,,czarna dziura”, mianowicie stan \(\emptyset=S_{x}\), gdzie \(x\) nie jest podsłowem \(w\). Dowieść, że liczbę przejść nie prowadzących do stanu \(\emptyset\) można oszacować z góry przez \(3n\).
Wskazówka. Wziąć drzewo rozpinające grafu automatu i oszacować liczbę pozostałych krawędzi przez liczbę sufiksów \(w\).
Opisany wyżej automat jest minimalny dla zbioru sufiksów. Tę samą konstrukcję można zastosować również do rozpoznawania zbioru wszystkich podsłów słowa \(w\), ale otrzymany automat nie musi być minimalny. Podać przykład.
Dowieść, że dla dowolnego automatu z \(\epsilon\)-przejściami istnieje zwykły automat skończony, który akceptuje ten sam język.
\(\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^{*})^{*}\).
\(\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}\).
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.
\(\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\).
zbiór słów nad alfabetem \(\{ a,b\}\), które zawierają dwa razy więcej \(a\) niż \(b\);
zbiór słów nad alfabetem \(\{ a,b\}\) o długości parzystej, w których liczba wystąpień litery \(b\) na pozycjach parzystych jest równa liczbie wystąpień tej litery na pozycjach nieparzystych;
Skonstruować gramatykę bezkontekstową jednoznaczną generującą język \(\mathbf{D_{1}}\) poprawnie uformowanych wyrażeń nawiasowych (por. Rozdział ??, Zadanie ?? ).
nie zawierają podsłowa (()).
Skonstruować gramatykę bezkontekstową jednoznaczną generującą język z Zadania ??.
Wskazówka. Rozważyć gramatykę
\(\displaystyle Z \rightarrow ZaZ^{+}b\,|\, ZbZ^{-}a\,|\,\varepsilon\)
\(\displaystyle Z^{+} \rightarrow Z^{+}aZ^{+}b\,|\,\varepsilon\)
\(\displaystyle Z^{-} \rightarrow Z^{-}bZ^{-}a\,|\,\varepsilon\)
Zauważyć związek miedzy produkcjami dla \(Z^{+}\) a poprzednim zadaniem (podobnie dla \(Z^{-}\)).
Dowieść, że następujące warunki są równoważne dla języka \(L\subseteq\Sigma^{*}\):
\(L\) jest regularny,
Czy zawsze istnieje gramatyka bezkontekstowa generująca \(L\) i mająca tylko jeden symbol nieterminalny ?
Wskazówka. Skonstruować automat niedeterministyczny równoważny wyrażeniu \(\beta\) i obliczyć zbiór stanów osiągalnych po słowie \(w\). Dla oszacowania w punkcie ?? użyć automatu z \(\epsilon\)-przejściami (por. zadanie ??.?? ), w grafie którego z każdego stanu wychodzą co najwyżej dwie krawędzie.
Rozważamy pytanie ,,\(w\in L[\beta]\) ?” jak w zadaniu ??, ale dla uogólnionego wyrażenia regularnego, tj. takiego, w którym dopuszczamy również operacje teorio–mnogościowe \(\cap\) i \(-\). Zaprojektować algorytm, który rozstrzyga to pytanie w czasie wielomianowym od \(|\beta|+|w|\).
Wskazówka. Zastosować metodę programowania dynamicznego:
dla \(1\leq i\leq j\leq|w|\) sukcesywnie obliczać zbiór podwyrażeń
\(\alpha\) wyrażenia \(\beta\) takich, że \(w[i..j]\in L[\alpha]\).
Konstrukcję automatu z zadań ??.?? i ??.?? , który dla danego \(w\) rozpoznaje język \(\Sigma^{*}w\), można przeprowadzić za pomocą następującego algorytmu. Niech \(m=|w|\).
Najpierw obliczamy pomocniczą tablicę \(F[0..m]\), taką, że \(F[0]=0\) oraz \(F[i]\) jest długością najdłuższego prefiksu właściwego \(w[1..i]\) będącego jednocześnie sufiksem \(w[1..i]\), dla \(i=1,\ldots,m\).
\(F[0]:=F[1]:=0\); \(i:=0\);
for \(j:=2\) to \(m\) do
begin \((*\, i=F[j-1]\,*)\)
while \(w_{j}\neq w_{{i+1}}\) \(\wedge\) \(i>0\) do \(i:=F[i]\);
if \(w_{j}=w_{{i+1}}\) then \(i:=i+1\);
\(F[j]:=i\)
end
W konstrukcji automatu przyjmujemy, że stany są liczbami \(0,1,\ldots,m\) (które można utożsamić z prefiksami \(w\) o odpowiednich długościach). Funkcję przejścia \(\delta\) określamy przez
Dowieść, że powyższy algorytm oblicza żądany automat w czasie liniowym względem długości \(w\) (zależnym od alafabetu).
Niech \(A\) będzie ustalonym automatem deterministycznym. Zaprojektować algorytm, który dla danej liczby \(n\) znajduje w czasie \({\cal O}(n)\) liczbę słów długości \(n\) akceptowanych przez \(A\).
Podać przykład świadczący o tym, że najkrótsze słowo, jakiego nie akceptuje automat niedeterministyczny o \(n\) stanach może mieć długość \(2^{{\Omega(n)}}\).
Wskazówka. Rozważyć automat akceptujący wszystko za wyjątkiem słowa
\((\ldots((a_{0}^{2}a_{1})^{2}a_{2})^{2}a_{3}\ldots a_{{n-1}})^{2}a_{n}.\)
Dowieść, że jeśli dwa stany \(n\)–stanowego automatu deterministycznego nie są równoważne (tzn. \(L(A,q)\neq L(A,p)\)), to istnieje słowo długości nie większej niż \(n\) akceptowane z dokładnie jednego z nich.
Wskazówka. Rozważyć zstępujący ciąg relacji równoważności na zbiorze stanów: \(R_{i}(p,q)\) o ile stany \(p\) i \(q\) są nierozróżnialne słowami długości \(\leq i\).
Uwaga. Zastosowanie idei zadania prowadzi do efektywniejszego algorytmu niż testowanie niepustości automatu produktowego.
Wskazówka. Rozważyć automat, którego graf jest pełnym grafem o \(n\) wierzchołkach, a każda krawęd”z ma inną etykietę. Stosując indukcję po \(n\), skonstruować pętlę, która ,,wymusza” eksponencjalną długość wyrażenia regularnego.
Eksplozja stanów w produkcie automatów. Niech \(\Sigma=\{ 0,1,\ldots,k\}\) i niech dla \(i=1,\ldots,k\), \(L_{i}\) będzie zbiorem słów \(v\) nad \(\Sigma\) o następującej własności:
\(i\) występuje w \(v\), ale przed pierwszym i pomiędzy kaźdymi dwoma kolejnymi wystąpieniami \(i\), \(i-1\) występuje co najmniej dwa razy.
Nietrudno jest skonstruować deterministyczny automat o 4 stanach rozpoznający \(L_{i}\). Dowieść, że każdy (nawet niedeterministyczny) automat rozpoznający język \(L_{1}\cap\ldots\cap L_{k}\) musi mieć co najmniej \(2^{{k+1}}-1\) stanów.
Wskazówka. Oszacować od dołu długość najkrótszego słowa w tym języku.
Dowieść, że jakikolwiek automat niedeterministyczny rozpoznający język \(\{ xcy:\, x,y\in\{ a,b\}^{*}\,\wedge\, x[1..k]=y[1..k]\}\) ma \(2^{{\Omega(k)}}\) stanów.
Zakładając, że następujący automat deterministyczny \(A_{n}\) ma \(n\) stanów (\(n\geq 2\), na rysunku \(n=6\)), dowieść, że jakikolwiek automat deterministyczny rozpoznający lustrzane odbicie języka \(L(A_{n})\) ma co najmniej \(2^{n}\) stanów (por. zadanie ?? na str. ?? ).
Słowo synchronizujące. Mówimy, że słowo \(w\) synchronizuje stany automatu deterministycznego, jeśli istnieje taki stan \(q_{0}\), że startując z dowolnego stanu i czytając słowo \(w\), automat dojdzie zawsze do stanu \(q_{0}\), tzn.
\((\forall q\in Q)\, q\stackrel{w}{\rightarrow}q_{0}\).
Znaleźć słowo synchronizujące dla automatu nad alfabetem \(\{ a,b\}\) o zbiorze stanów \(\{ 0,1,\ldots,k-1\}\) i funkcji przejścia
\(i\stackrel{a}{\rightarrow}i+1\;\;(\textrm{mod}k)\)
dla \(i=0,1,\ldots,k-1\)
\(i\stackrel{b}{\rightarrow}i\)
dla i = 0,1, …, k-2
\(k-1\stackrel{b}{\rightarrow}0\)
Wskazówka. Dla k=5 słowem synchronizującym (najkrótszym) jest \(w=\left(ba^{4}\right)^{3}b\)
Zaprojektować algorytm, który dla automatu o \(n\) stanach rozstrzyga w czasie \({\cal O}(n^{3})\), czy istnieje słowo synchronizujące i w pozytywnym przypadku znajduje takie słowo (długości \(\leq(n-1)^{3}\)).
Wskazówka. Dla każdej pary stanów sprawdzamy, czy istnieje słowo synchronizujące dla tej pary. Szukamy ścieżki w grafie
par od danej pary do pary o identycznych składowych. Wystarczy jeden taki graf dla wszystkich par.
Graf ma rozmiar kwadratowy. Zatem pare można zsynchronizować słowem długości kwadratowej.
Zaczynamy od zbioru wszystkich stanów. Stosując słowo do jednej pary sklejamy je w jeden stan. Teraz mamy juz tylko n-1
stanów. Znowu bierzemy parę róznych słów. Dla niej liczymy słowo synchronizujące
(w czasie kwadratowym) i sklejamy te stany. Kontynuujemy aż skleimy wszystkie stany do jednego stanu.
(*) Znaleźć najkrótsze słowo synchronizujące dla automatu z punktu ().
Uwaga. Licząca już 40 lat hipoteza Černego, zobacz www.liafa.jussieu.fr/\(\sim\)jep/Problemes/Cerny.html , głosi, że najkrótsze słowo synchronizujące, o ile istnieje, ma długość \((n-1)^{2}\).
Wskazówka. Skonstruować automat skończony, rozpoznający hipotetyczne słowa posiadające dwie różne faktoryzacje.
\(\forall\ (x\in L)\ \forall\ (r,\ s\in\Sigma\ )\ \# _{{r}}(x)=\# _{{s}}(x).\)
Dany jest (poprzez automat skończony) język regularny \(L\) nad skończonym alfabetem \(\Sigma\), sprawdzić czy dla wszystkich słów \(x\in L\) poza skończoną ilością zachodzi
\(\forall\ (r,\ s\in\Sigma\ )\ r\ne s\ \Rightarrow\ \# _{{r}}(x)\ \ne\ \# _{{s}}(x).\)
\(L\ =\ \{ u\$ w^{R}\ :\ u,w\in\{ a,b\}^{+},\ w\textrm{ jest prefiksem i sufiksem }u\ \}\)
To samo pytanie dla dopełnienia tego jezyka.
Udowodnić, że język \(L\ =\ \{ a^{i}b^{j}c^{k}\ :i\ne j,\ i\ne k,\ j\ne k\ \}\) nie jest bezkontekstowy.
Czy jego dopełnienie jest bezkontekstowe ?
Czy jego dopełnienie jest bezkontekstowe ?
\(\{\mbox{bin}(n)\,\$\,\mbox{bin}(n^{2})^{R}\,:\, n\in N\},\)
gdzie \(\mbox{bin}(n)\in\{ 0,1\}^{*}\) jest binarnym przedstawieniem liczby \(n\), jest bezkontekstowy?
\(\ L_{4}\ =\ \{\ [n]_{2}\;[2n]_{2}\ :\ n\ge 1\ \}\)
\(\displaystyle F \to \mbox{\bf true}\,|\,\mbox{\bf false}\,|\, V\,|\,(F\vee F)\,|\,(F\wedge F)\,|\,(\neg F)\)
\(\displaystyle V \to xI\)
\(\displaystyle I \to 0\,|\, 1J\)
\(\displaystyle J \to J0\,|\, J1\,|\,\epsilon\)
Np. \(((x101\vee(\neg x0))\wedge(\neg(\mbox{\bf false}\vee x101)))\) jest formułą.
Udowodnij, że zbiór wszystkich tautologii nie jest bezkontekstowy. Stwierdzenie to wynika łatwo z hipotezy P \(\neq\) NP, ale należy je dowieść bez tej hipotezy..
Czy zbiór słów Lyndona jest bezkontekstowy ?
Wskazówka: we”zmy \(a^{{n+1}}ba^{n}ba^{n}\) i zastosujmy lemat Ogdena, ,,markując” środkową grupę \(a^{n}\).
L bezkontekstowy \(\Longrightarrow\) \(L\cap PAL\) bezkontekstowy ?
Sformuluj \(uvwxy\)-lemat o pompowaniu dla języków liniowych w którym \(|uvxy|=O(1)\).
Dowied”z, że język \(\{ a^{i}b^{i}c^{j}d^{j}:i,j\in{\bf N}\}\) nie jest liniowy.
Dowied”z, że \(L\ =\ \{ x\in(a+b)^{*},\# _{a}(x)=\# _{b}(x)\}\) nie jest liniowym językiem bezkontekstowym.
Który z następujących języków jest bezkontekstowy. W przypadku gdy język jest bezkontekstowy wypisać gramatykę bezkontekstową. W zadaniu \([x]_{2}\) oznacza binarny zapis liczby \(x\), oraz \(w^{R}\) oznacza odwrócenie słowa \(w\).
Skonstruować automaty ze stosem rozpoznające poznane wcześniej języki bezkontekstowe: zbiór palindromów, zbiór poprawnie uformowanych ciągów nawiasów, zbiór słów, które mają dwa razy więcej \(b\) niż \(a\), zbiór ciągów, które nie są postaci \(ww\).
\(\{\mbox{bin}(n)\,\$\,\mbox{bin}(n+1)^{R}\,:\, n\in N\}\)
\(\{\mbox{bin}(n)\,\$\,\mbox{bin}(3*n)^{R}\,:\, n\in N\}\)
Uogólnić tezę zadania.
\(q,a,Z\,\rightarrow _{{A^{{\prime}}}}\, q^{{\prime}},\alpha\)
gdzie \(|\alpha|\leq 2\) (\(q,q^{{\prime}}\) dowolne).
Dowieść, że dla każdego automatu ze stosem \(A\), można skonstruować równoważny mu automat ze stosem \(A^{{\prime\prime}}\), w którym każde przejście jest postaci push lub pop, tzn.
\(q,a,Z\,\rightarrow _{{A^{{\prime\prime}}}}\, q^{{\prime}},YZ\)
lub
\(q,a,Z\,\rightarrow _{{A^{{\prime\prime}}}}\, q^{{\prime}},\epsilon\)
Czy dla takich automatów można nadal ograniczyć liczbę stanów?
Mając dany automat ze stosem akceptujący język \(L\), skonstruować automaty ze stosem akceptujące następujące języki:
Mając dany automat ze stosem akceptujący język \(L\) i automat skończony akceptujący język \(R\), skonstruować automaty ze stosem akceptujące następujące języki:
Niech \(\# _{s}(w)\) oznacza liczbę symboli \(s\) w słowie \(w\), oraz \(PREF(u)\) oznacza zbiór prefiksów słowa \(u\). Ponadto oznaczmy przez \(max(w),\ min(w),\ med(w)\) opowiednio maksimum, minimum i medianę liczb \(\# _{a}(w),\# _{b}(w),\# _{c}(w)\).
Który z następujących języków jest regularny, a który bezkontekstowy?
\(\{\alpha\in\Gamma^{*}\,:\,(\exists w,v\in\Sigma^{*})(\exists q\in Q)\, q_{I},w,Z_{I}\,\vdash _{{A}}\, q,v,\alpha\}\)
Wywnioskować stąd, że zbiór słów, które są możliwymi zawartościami stosu automatu \(A\) w jakimś obliczeniu akceptującym, jest językiem bezkontekstowym.
jeśli, dla pewnej pary \(q,Z\), zachodzi \(q,\epsilon,Z\rightarrow _{A}p,\alpha\) przy pewnych \(p,\alpha\), to dla żadnego \(\sigma\in\Sigma\), nie zachodzi \(q,\sigma,Z\rightarrow _{A}p^{{\prime}},\alpha^{{\prime}}\), dla żadnych
\(p^{{\prime}},\alpha^{{\prime}}\);
Język bezkontekstowy jest deterministyczny jeśli jest rozpoznawany przez pewien deterministyczny automat ze stosem (w sensie stanów akceptujących, tzn. \(L=L(A)\)).
Dowieść, że język \(\{ a^{n}b^{n}:n\in{\bf N}\}\) \(\cup\) \(\{ a^{n}b^{{2n}}:n\in{\bf N}\}\) nie jest deterministycznym językiem bezkontekstowym.
Wskazówka. Zakładając, że istnieje deterministyczny automat \(A\) rozpoznający ten język, rozważyć automat \(A^{{\prime}}\), który różni się od \(A\) tylko tym, że zamienia rolami \(a\) i \(b\). Przy pomocy tych dwóch automatów można łatwo skonstruować automat ze stosem rozpoznający język \(\{ a^{n}b^{n}a^{n}:n\in{\bf N}\}\).
Wykazać, że zbiór palindromów nad alfabetem dwuelementowym nie jest deterministycznym językiem bezkontekstowym.
Wskazówka. Zastosować metodę z poprzedniego zadania. Przy pomocy hipotetycznego automatu deterministycznego rozpoznającego palindromy można np. skonstruować automat rozpoznający język \(\{ ca^{n}ba^{n}ca^{n}ba^{n}c:n\in{\bf N}\}\).
\(h(a)=a,\ h(b)=b,\ h(a^{{\prime}})=a,\ h(b^{{\prime}})=b\)
oraz \(h(x)=\epsilon\) dla symboli \(x\in\{ a,b,a^{{\prime}},b^{{\prime}}\}\) dla których morfizm nie został zdefiniowany powyżej. Wykazać, że język \(EQ(h,g)=\{ w:h(w)=g(w)\}\) nie jest bezkontekstowy.
Język ma własność prefiksową, gdy dla każdych dwóch słow z tego języka jedno z nich jest prefiksem drugiego. Wykaż, że jeśli język bezkontekstowy ma własność prefiksową to jest on regularny.
\(\{ h(u)c(g(u))^{R}\ :\ u\in L\}\)
Udowodnij, że przecięcie liniowego języka bezkontekstowego z regularnym jest językiem liniowym.
Zbiór \(\mbox{Max}(L)\) określamy analogicznie jak zbiór \(\mbox{Min}(L)\) w zadaniu ??. Podaj przykład języka bezkontekstowego \(L\), dla którego \(\mbox{Max}(L)\) nie jest językiem bezkontekstowym.
Udowodnij, że zbiór długości słów języka bezkontekstowego jest semi-liniowy.
\(d(u,w)=|\{ i:w_{i}\neq v_{i}\}|.\)
Udowodnić, że dla języka regularnego \(L\), język
\(\{\ w\ :\ (\exists\ u\in L)\ |u|=|w|\ \textrm{oraz}\ d(u,w)\le\frac{|u|}{2}\ \}\)
jest bezkontekstowy. Czy język ten jest zawsze regularny ?
To samo, ale wymagamy dodatkowo, aby \(L\) był bezkontekstowy.
(*) Dowieść, że maszyny typu write-once z jedną taśmą akceptują jedynie języki regularne.
Automat z \(k\) licznikami \(c_{1},\ldots,c_{k}\), określamy podobnie jak automat z \(k\) stosami, z tym, że liczniki zawierają liczby naturalne, a dostępne operacje na licznikach są postaci \(c_{i}:=c_{i}+1\), \(c_{i}:=c_{i}\dot{-}1\) (gdzie \(0\dot{-}1=0\)), oraz test \(c_{i}\stackrel{?}{=}0\). Tzn. przejścia takiego automatu są postaci \(q\rightarrow p\), \(q,c_{i}\stackrel{?}{=}0\rightarrow p\), \(q,c_{i}\stackrel{?}{\neq}0\rightarrow p\), \(q\rightarrow p,c_{i}:=c_{i}+1\), \(q\rightarrow p,c_{i}:=c_{i}\dot{-}1\). Nie ma taśmy, lecz zakładamy, że w chwili początkowej dana wejściowa jest wartością licznika \(c_{1}\), a pozostałe liczniki mają wartość 0. Dowieść najpierw, że dla każdej maszyny Turinga nad alfabetem \(\{ 1\}\) istnieje równoważny jej automat z 4 licznikami. Następnie wykazać, że liczba liczników może być dalej zredukowana do trzech. (Ograniczenie alfabetu maszyny Turinga nie jest istotne, bo słowa nad alfabetem \(n\)–literowym można również łatwo “przerobić” na liczby naturalne w systemie unarnym.)
Dane są dwie listy słów : \(u_{1},\ldots,u_{n}\in\Sigma^{*}\) i \(w_{1},\ldots,w_{n}\in\Sigma^{*}\). Pytanie, czy istnieje ciąg indeksów \(i_{1},\ldots,i_{m}\in\{ 1,\ldots,n\}\), taki, że \(u_{{i_{1}}}\ldots u_{{i_{n}}}=w_{{i_{1}}}\ldots w_{{i_{n}}}\) ? Jeśli taki ciąg istnieje, to słowo \(u_{{i_{1}}}\ldots u_{{i_{n}}}\) (\(=w_{{i_{1}}}\ldots w_{{i_{n}}}\)) nazywamy rozwiązaniem danej instancji problemu Posta.
Wskazówka : Rozważyć zmodyfikowany problem Posta, w którym dodatkowo wymaga się, by pierwszymi słowami w rozwiązaniu były \(u_{1}\) i \(w_{1}\) (tzn. \(i_{1}=1\)). Redukcja zmodyfikowanego problemu do oryginalnego problemu Posta nie jest trudna. Z kolei przedstawić algoerytm, który dla dowolnej maszyny Turinga \(M\) i jej wejścia \(w\) konstruuje instancję \(P\) zmodyfikowanego problemu Posta w ten sposób, że \(P\) ma rozwiązanie wtedy i tylko wtedy, gdy \(M\) akceptuje \(w\). Rozwiązaniem \(P\) (o ile istnieje) będzie właśnie akceptujące obliczenie \(M\) na \(w\).
Czy następuący problem \(X\) jest rozstrzygalny:
Dana gramatyka bezkontekstowa \(G\), sprawdzić czy \(L(G)\) zawiera palindrom.
Załóżmy, że wiemy że jednotasmowa deterministyczna maszyna Turinga \(M\) wykonuje zawsze co najwyzej jeden ńawrót” (to znaczy glowica przesuwa sie w prawo a od pewnego momentu już tylko w lewo). Czy problem “\(w\in L(M)\)” jest rozstrzygalny, gdzie \(w\) jest słowem wejściowym a \(L(M)\) oznacza zbiór słów akceptowanych przez \(M\) stanem akceptującym.
Czy następujący problem jest rozstrzygalny. Dane są dwa słowa \(u,w\in\Sigma^{*}\) oraz liczba \(k\), sprawdzić czy
\(\left(\exists\ x\in\Sigma^{*}\right)\ \left(\ |x|>k\ \&\ \mathit{Ile}(w,x)=\mathit{Ile}(u,x)\ \right)\)
gdzie \(\mathit{Ile}(w,x)\) oznacza liczbę wystąpień słowa \(w\) jako podsłowo \(x\) (wystąpienia nie muszą być rozłączne).
Niech \(\mathit{bin}(n)\) oznacza zapis binarny liczby naturalnej \(n\). Mamy \(|\mathit{bin}(n)|=\lfloor\log _{2}n\rfloor+1\) z wyjątkiem liczby 0, dla której \(|\mathit{bin}(0)|=1\). Określić obliczalną różnowartościową funkcję pary \(\{ 0,1\}^{*}\times\{ 0,1\}^{*}\), tak by
\(|(x,y)|=|x|+|y|+\min\{|\mathit{bin}(|x|)|,|\mathit{bin}(|y|)|\}+{\cal O}(1)\)
Ustalamy pewne kodowanie maszyn Turinga, które pozwala nam utożsamiać maszynę \(M\) z pewnym słowem nad \(\{ 0,1\}\). Rozważmy funkcję \(C\), która parze \(\left(M,v\right)\) przyporządkowuje minimalną długość słowa \(x\), takiego że
\(M(x)=v\)
lub specjalny symbol \(\infty\), gdy nie ma takiego \(x\).
Wskazówka. W przeciwnym razie obliczalna byłaby również funkcja, która liczbie \(n\) danej w postaci binarnej przyporządkowuje pewne słowo \(w\in(0+1)^{n}\), takie że
\(\min\{|(M,x)|:M(x)=w\}\geq n\)
(długość pary w rozumieniu za zadania ??). Biorąc za \(M\) maszynę obliczajacą tę funkcję oraz \(\mathit{bin}(n)\) za \(x\), otrzymujemy sprzeczność.
Uwaga. Nie ma sprzeczności pomiędzy punktami ?? i ?? , ponieważ odbiorca powyższego ciągu nigdy nie wie, czy jest on już ustalony.
gdzie \(X\in V\), \(\alpha,\beta,\gamma\in(\Sigma\cup V)^{*}\), \(\gamma\neq\varepsilon\) (\(V\) – zbiór symboli nieterminalnych, \(\Sigma\) – zbiór symboli terminalnych).
Uwaga. Przy powyższym sprowadzeniu trzeba na ogół powiększyć zbiór symboli nieterminalnych.
Uwaga. Automaty liniowo ograniczone są określone podobnie jak maszyny Turinga, z tym, że jedyną dostępną pamięcią są komórki taśmy zajęte na początku przez słowo wejściowe (przy czym koniec słowa jest zaznaczony specjalnym markerem).
Wskazówka. Wykorzystać język obliczeń maszyny Turinga, która akceptuje język nieobliczalny.
Wywnioskować dalej, że ani języki kontekstowe, ani języki obliczalne nie są zamknięte na ilorazy przez języki regularne.
Które z czterech klas hierarchii Chomsky'ego są zamknięte na operacje \(\cup,\cap,-\) ?
\(f(n)=2n,n^{2},n^{k},2^{n},\log n,\ldots\)
Należy udowodnić, że problem domina jest NP-zupełny. Wskazówka : zastosować redukcję generyczną, tzn. wychodząc od dowolnej niedeterministycznej maszyny Turinga działającej w czasie wielomianowym.
Udowodnić, że następujący problem dokładnego pokrycia (ang. exact cover) jest NP-zupełny. Dana rodzina podzbiorów \(\{ 1,2,\ldots,n\}\) (liczby dane binarnie). Pytanie: czy istnieje podrodzina podzbiorów rozłącznych, które w sumie dają \(\{ 1,2,\ldots,n\}\).
Wskazówka : wykorzystać zadanie ??.
Wskazówka : wykorzystać zadanie ??.