\documentclass[12pt,polish]{article}
%\usepackage{epsfig}
%\usepackage{firma77}
\usepackage{amsmath}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{babel}
\usepackage{latexsym}
\usepackage{eurosym}
\usepackage{psfig}
\input xy
\xyoption{all}
\RequirePackage[dvipdf]{graphicx}
\advance\hoffset-2.5truecm
%\advance\voffset-4.2truecm
\advance\voffset-2.5truecm
\textwidth16truecm
\textheight23truecm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Time %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\newcount\hour \hour=\time
\newcount\minute \minute=\hour
\divide\hour by 60
\newcount\temp \temp=\hour
\multiply\temp by 60
\advance\minute by -\temp
\newcount\temp \temp=\minute
\divide\temp by 10
\def\optzero{\ifcase\temp 0\fi}
\def\czas{\number\hour :$\,$\optzero\number\minute}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Date %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\miesiaca{\ifcase\month\or stycznia\or lutego\or marca\or kwietnia\or maja
                           \or czerwca\or lipca\or sierpnia\or wrze\'snia
                           \or pa\'zdziernika\or listopada\or grudnia\fi}
\def\dzisiaj{\ \number\day\ \miesiaca\ \number\year} 
%%%%%%%%%%%%%%%%%%%%%%% Style changes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{Zadanie}{Zadanie}
\newtheorem{twierdzenie}{Twierdzenie}
\newtheorem{Lemat}{Lemat}
\newtheorem{Fakt}{Fakt}
\newtheorem{Wniosek}{Wniosek}
\newtheorem{Przyklad}{Przyk"lad}
\newtheorem{Pytanie}{Pytanie}
\newtheorem{Cwiczenie}{"Cwiczenie}
\newtheorem{Obserwacja}{Obserwacja}
\newcommand{\dom}{\mbox{dom\,}}
\newcommand{\Pal}{\mbox{Pal\,}^{>1}}
\newcommand{\Nat}{{\bf N}}
\title{{\large J\c{e}zyki, Automaty i Obliczenia}\\
Zadania }
\author{Damian Niwi\'{n}ski i Wojciech Rytter}
\date{\today }
%%%%%\date{Pa\'{z}dziernik 1999}
\begin{document}

\pagestyle{myheadings}
\markboth{JAiO --- Zadania}{JAiO --- Zadania }
\maketitle

\paragraph{Podziękowania.} Autorzy dziękują Wszystkim, w szczególności
Studentom, którzy sygnalizowali błędy, sugerowali nowe zadania lub
podali ciekawe (i poprawne :) rozwiazania.

\section{S"lowa, liczby, grafy}\label{section:slowa}
Do tej partii zada"n mo"re podej"s"c Czytelnik bez "radnej
znajomo"sci teorii automat"ow.
\begin{enumerate}
\item {\em S"lowa pierwotne.}
S"lowo $w \in \Sigma^* $ nazywamy {\em pierwotnym} (ang. {\em primitive}),
je"sli nie da si"e go przedstawi"c $ w = v^n $, inaczej ni"r dla $n=1$ i
$v=w$. 
\begin{enumerate}
\item
Dowie"s"c, "re dla ka"rdego s"lowa niepustego $w$, istnieje 
{\em dok\l adnie jedno} s"lowo pierwotne $v$, takie  "re $ w = v^n $, 
dla pewnego $n \geq 1$.

Liczb"e $n$ nazywamy {\em wyk\l adnikiem} s"lowa $w$.
\item
O s"lowach $wv$ i $vw$ m"owimy, "re s"a w {\em relacji koniugacji}.
Dowie"s"c, "re jest to relacja r"ownowa"rno"sci.

Dowie"s"c, "re dwa s"lowa b"ed"ace w relacji koniugacji maj"a ten sam
wyk"ladnik.
Jaka jest moc klasy abstrakcji relacji koniugacji dla s"lowa o d"lugo"sci
$m$ i wyk"ladniku $n$? 
%($m/n$)
\end{enumerate}
\item {\em J"ezyk nawiasowy.} \label{nawiasy}
Wykaza"c, "re zbi"or poprawnie uformowanych ci"ag"ow nawias"ow mo"re
by"c zdefiniowany na dwa {\em r"ownowa"rne} sposoby:
\begin{itemize}
\item Jako najmniejszy zbi"or $L$ zawieraj"acy ci"ag pusty oraz taki, "re
je"sli $w,v\in L$, to r"ownie"r $(w) , wv \in L$.
\item Zbi"or s"l"ow nad alfabetem $\{ (,) \}$, w kt"orych ilo"s"c ``)''
jest taka sama jak ilo"s"c ``('', a w ka"rdym prefiksie
ilo"s"c ``)''
jest niewi"eksza ni"r ilo"s"c ``('' .
\end{itemize}
\item {\em Zbiory semi--liniowe.} \label{semi-liniowe}
Zbi"or liczb naturalnych postaci $\{ a+bn\, : \, n \in \Nat \}$, dla ustalonych
$a,b \in \Nat$ nazywamy {\em liniowym}. Zbi"or bed"acy sum"a sko"nczonej
liczby zbior"ow liniowych nazywamy {\em semi\-li\-nio\-wym}. (Gdy sumowana 
rodzina jest pusta, otrzymujemy zbi"or pusty.)

\begin{enumerate}

\item
Dowie"s"c, "re ka"rdy zbi"or postaci 
$\{ a+b_1 n_1 + \ldots + b_k n_k \, : \, n_1, \ldots ,n_k  \in \Nat \}$, 
dla ustalonych $k$ i 
$a,b_1 ,\ldots ,b_k  \in \Nat$,  jest semi--liniowy.


{\em Wskaz"owka.\/} Wykorzysta"c podzia"ly zbioru liczb naturalnych
na klasy abstrakcji relacji przystawania {\em modulo\/} $m$, dla
odpowiednio dobranych liczb $m$.


\item
Dowie"s"c, "re zbi"or liczb naturalnych $A$ jest semi--liniowy
wtedy i tylko wtedy, gdy jest prawie periodyczny tzn.~gdy istniej"a
$c \in \Nat $ i $d \in \Nat - \{ 0 \}$ takie, "re dla ka"rdego
$x > c$, $x \in A \, \Leftrightarrow  \, x+d \in A$.



\item
W grafie zorientowanym ustalamy dwa wierzcho"lki. Interesuje nas zbi"or
d"lugo"sci wszystkich mo"rliwych "scie"rek pomi"edzy tymi wierzcho"lkami.
Dowie"s"c, "re jest to zbi"or semi--liniowy.

\item
Dowie"s"c, "re rodzina zbior"ow semi--liniowych jest zamkni"eta na
sko"nczone sumy, przeci"ecia oraz na uzupe"lnienie wzgl"edem $N$.


\end{enumerate}

\item {\em Graf gry (J.~P.~Jouannaud).\/} 
Rozwa"ramy nast"epuj"ac"a gr"e pomi"edzy Barmanem
i Klientem. Przed  Barmanem na obrotowym talerzu stoj"a
cztery szklanki tworz"ac wierzcho"lki kwadratu. Szklanka
mo"re by"c ustawiona normalnie lub dnem do g"ory, jednak
Barman ma przepask"e na oczach i r"ekawiczki na r"ekach,
tak "re nie mo"re tego zobaczy"c ani wyczu"c. Ruch Barmana
polega na odwr"oceniu jednej lub dw"och dowolnie wybranych
szklanek. Ruch Klienta polega na obr"oceniu talerza
(o wielokrotno"s"c "cwier"c-obrotu).
Barman wygrywa, je"sli w jakim"s momencie gry wszystkie
szklanki ustawione s"a w tej samej pozycji (zostanie o tym
lojalnie poinformowany).

Czy Barman no"re wygra"c startuj"ac z nieznanej konfiguracji
pocz"atkowej, a je"sli tak, to w jakiej liczbie ruch"ow?

Czy graliby Pa"nstwo o pieni"adze z Barmanem~? A gdyby zamiast
kwadratu by"ly 3 szklanki ustawione w tr"ojk"at lub 5 
w pi"eciok"at~?
\item \label{kody} {\em Kody.} 
Zbi"or $C\subseteq \Sigma^+ $ nazywamy {\em kodem}, je"sli ka"rde s"lowo
$w\in \Sigma^* $ dopuszcza co najwy"rej jedn"a faktoryzacj"e wzgl"edem
$C$ (tzn., da si"e ``odkodowa"c'').

Niech $\Sigma = \{ a,b \} $. Dowie"s"c, "re zbi"or $\{ aa, baa, ba \} $
jest kodem, a zbi"or $\{ a, ab, ba \}$ nie jest.

Je"sli sko"nczony zbi"or $C$ nie jest kodem, oszacowa"c z g"ory 
d"lugo"s"c najkr"otszego s"lowa, kt"ore o tym "swiadczy
(tzn.~dopuszcza dwie r"o"rne faktoryzacje).

Patrz też rozdz. \ref{algorytmy}, zadanie \ref{drugie_kody}.

%%%%%%(Poda"c wielomianowy algorytm sprawdzania, czy dany sko"nczony zbi"or
%%%%%%($C$ jest kodem.

%%%%%%({\em Wskaz"owka.} Mo"rna rozwa"ry"c graf, kt"orego wierzcho"lkami s"a
%%%%%%(sufiksy s"l"ow z $C$, a kraw"ed"z z $v$ do $u$ prowadzi wtedy, gdy 
%%%%%%($(\exists w \in C)\, w = v u $. Wtedy rozwi"azanie naszego problemu
%%%%%%(mo"rna wydedukowa"c z przeszukania tego grafu.
\end{enumerate}

\section{J"ezyki regularne}
\subsection{Automaty sko"nczone i wyra"renia regularne}
\label{subsection:automaty}
\begin{enumerate}
\item Dowie"s"c, "re dla dowolnych j"ezyk"ow $L, M$,
$(L^* M^* )^* = (L \cup M)^* $.
\item Dowie"s"c, "re wyra"renie regularne
$(00 + 11 + (01 + 10) (00 + 11)^* (10 + 10))^*$ reprezentuje
zbi"or wszystkich s"l"ow nad alfabetem $\{ 0,1 \}$, w kt"orych
zar"owno liczba wyst"apie"n 0 jak i liczba wyst"apie"n 1 s"a parzyste.

Jak najkr"ocej reprezentowa"c zbi"or s"l"ow, w kt"orych te liczby s"a
tej samej parzysto"sci?

\item Zbudowa"c automat nad alfabetem $\{ 0,1 \}$, rozpoznaj"acy
s"lowa, w kt"orych liczba jedynek na pozycjach parzystych jest parzysta,
a liczba jedynek na pozycjach nieparzystych jest nieparzysta.

\item \label{plus}
{\em Dodawanie.} Rozwa"ramy s"lowa nad alfabetem $\{ 0,1\}^3$.
Powiemy, "re s"lowo $ \langle a_1,b_1,c_1 \rangle $ \ldots
$\langle a_n ,b_n ,c_n \rangle $ d"lugo"sci $n$ {\em reprezentuje
dodawanie\/}, je"sli liczba reprezentowana binarnie przez s"lowo
$c_1 \ldots c_n$ jest sum"a liczb reprezentowanych przez 
$a_1 \ldots a_n$ i $b_1 \ldots b_n$. Na przyk"lad, ci"ag
$\langle 0,0,1 \rangle  \langle 1,1,1 \rangle 
\langle  0,1,0 \rangle \langle 1,1, 0\rangle $ reprezentuje
dodawanie (5+7=12). Poda"c wyra"renie regularne opisuj"ace zbi"or
wszystkich s"l"ow nad alfabetem $\{ 0,1\}^3$ reprezentuj"acych dodawanie
w powy"rszym sensie.
\item {\em Podzielno"s"c.}
\begin{enumerate}
\item
Skonstruowa"c sko"nczony
automat deterministyczny nad alfabetem $\{ 0,1,\ldots ,8,9\}$
rozpoznaj"acy 
 zbi"or  dziesi"etnych reprezentacji wielokrotno"sci liczby 7.
\item Jak wy"rej, ale przy reprezentacji odwrotnej, tj.~poczynaj"ac
od cyfr najmniej znacz"acych. 
%\item zbi"or s"l"ow, kt"orych lustrzane odbicia s"a podzielne przez 7.
%\item Skonstruowa"c automat {\em deterministyczny} rozpoznaj"acy
%zbi"or z poprzedniego punktu.
\item Uog"olni"c niniejsze zadanie.
\end{enumerate}
\item {\em Alfabet jednoliterowy.}
%%\begin{enumerate}
%%\item 
Dowie"s"c, "re j"ezyk $L \subseteq \{ a \}^*$ jest regularny
wtedy i tylko wtedy, gdy zbi"or liczb naturalnych
$\{ n : a^n \in L \}$ jest semi--liniowy w sensie 
rozdzia"lu~\ref{section:slowa}.
%%\item 
Dowie"s"c, "re dla dowolnego zbioru 
$X \subseteq \{ a \}^*$, j"ezyk $X^*$ jest regularny.
%%\end{enumerate}
\item {\em Zbiory semi--liniowe}
(por.~zadanie~\ref{semi-liniowe}  
z rozdzia"lu~\ref{section:slowa}). 
\begin{enumerate}
\item Dowie"s"c, "re dla dowolnego j"ezyka regularnego $L$ zbi"or
$\{ |w| : w \in L \}$ jest semi--liniowy. 

W szczeg"olno"sci, j"ezyki regularne nad {\em jednoliterowym\/} alfabetem
mog"a by"c uto"rsamiane ze zbiorami semi--liniowymi poprzez bijekcj"e
$w \mapsto |w|$.
\item \label{maly Cobham}
Dowie"s"c, "re je"sli
$M \subseteq \Nat$ jest zbiorem semi--liniowym, to
j"ezyk $\{ \mbox{bin} (m) :$ $m\in M \}$ jest regularny, gdzie
$\mbox{bin} (m)$ oznacza binarn"a reprezentacj"e liczby $m$.
\end{enumerate}
{\em Uwaga.} Fakt analogiczny 
do~\ref{maly Cobham} mo"rna udowodni"c dla dowolnej reprezentacji,
a zatem zbi"or semi--liniowy jest regularny w reprezentacji o podstawie
$k$,
%w ka"rdej $k$--arnej reprezentacji, 
dla $k \geq 1$. W przeciwnym kierunku wiadomo, "re je"sli
zbi"or jest regularny w reprezentacjach o wzgl"ednie pierwszych
podstawach  $p$ i $q$, to jest semi--liniowy --- jest to
wniosek z g"l"ebokiego Twierdzenia
Cobhama.

\item Dowie"s"c, "re dla danych liczb $a,b,p,r \in \Nat$, j"ezyk
\[ L \, = \, \{ \, \mbox{bin} (x) \, \$  \, \mbox{bin} (y)  \, : 
( a \cdot x + b \cdot y )
\equiv r \pmod{p} \} \]
jest regularny.
\end{enumerate}
Przyk"lady automat"ow zwi"azanych z rozpoznawaniem wzorca
Czytelnik znajdzie poni"rej w punkcie~\ref{wzorce}.

\subsection{Lemat o pompowaniu} \label{pompa}
%%%%\item 
\begin{enumerate}
\item Dowie"s"c, "re nast"epuj"ace j"ezyki nie s"a regularne:
\begin{itemize}
\item $\{ a^n b^n \, :\, n\in N \} $
\item $\{ a^{2^n }\, :\, n\in N \} $
\item $\{ a^{p}\, :\, p \mbox{  jest liczb"a pierwsz"a} \} $
\item $\{ a^{i}b^j \, :\, \mbox{nwd}(i,j) = 1 \} $
\item $\{ a^m b^n \, :\, m \neq n  \} $
\item $\{ \mbox{bin} (p) \, :\, p \mbox{  jest liczb"a pierwsz"a} \} . $
\end{itemize}
\item Dowie"s"c, "re zbi"or palindrom"ow nad alfabetem o co najmniej
dw"och elementach nie jest regularny.
\item Dowie"s"c, "re zbi"or wyra"re"n regularnych nie jest regularny.
\item Dowie"s"c, "re je"sli w Zadaniu~\ref{plus} 
z punktu~\ref{subsection:automaty} zamienimy
{\em dodawanie\/} przez {\em mno"renie\/}, to otrzymany j"ezyk
(nad alfabetem $\{ 0,1\}^3$) jest wprawdzie dobrze okre"slony, ale
nie jest regularny.

\item Udowodni"c nieco silniejszy wariant Lematu o pompowaniu:

Je"sli $L$ jest regularny, to
\begin{quote}
{\bf (*)} Istnieje sta"la $n_0$, "re dla ka"rdych s"l"ow
$v,w,u$ takich "re $|w| \geq n_0$ i $vwu \in L$, istniej"a
$x,y,z$ takie, "re $ w = xyz $,  $0 < |y| \leq n_0$, oraz
$\forall n \in \Nat, \,   v x y^n z u \in L$.
\end{quote}
Poda"c przyk"lad j"ezyka $L$, kt"ory spe"lnia (*), cho"c
nie jest regularny.

{\em Wskaz"owka.} 
$\sum_p \underbrace{c b^* c b^* \ldots  c b^* }_p + (b+c)^* cc(b+c)^*$,
gdzie $p$ przebiega liczby pierwsze.

\end{enumerate}
\subsection{W"lasno"sci domkni"ecia j"ezyk"ow regularnych} \label{properties_reg}
\begin{enumerate}
\item Dowie"s"c, "re dla j"ezyka regularnego $L \subseteq \Sigma^*$
i dowolnego zbioru $X \subseteq \Sigma^*$ j"ezyki
\begin{eqnarray*}
X^{-1} L & = &  \{ w : \, (\exists v \in X) \, v w \in L \}
\end{eqnarray*} 
i
\begin{eqnarray*}
 L X^{-1} & =  &  \{ w : \, (\exists u \in X) \,  w u \in L \}
\end{eqnarray*}  
s"a regularne.
\item Dowie"s"c, "re  j"ezyk $L$ jest regularny wtedy i tylko wtedy,
gdy j"ezyk $L^R$ s"l"ow stanowi"acych lustrzane odbicia s"l"ow z $L$
jest regularny.

{\em Uwaga.\/} Lustrzane odbicie $w^R$ s"lowa $w$ mo"remy w "scis"ly spos"ob
zdefiniowa"c rekurencyjnie: $\epsilon^R = \epsilon $ i
$(w \sigma )^R = \sigma w^R $, dla $w \in \Sigma^*$, $\sigma \in \Sigma $.

\item Dla danego automatu $A$ rozpoznaj"acego j"ezyk $L$, 
skonstruowa"c automat rozpoznaj"acy
j"ezyk 
\[  \mbox{\em Cycle}(L) = \{ vu \, :\, uv \in L \} \]
Czy z faktu, "re j"ezyk
$\mbox{\em Cycle}(L) = \{ vu \, :\, uv \in L \} $ jest regularny, mo"rna
wnioskowa"c, "re j"ezyk $L$ jest regularny?
\item Niech $L$ bedzie j"ezykiem regularnym nad alfabetem $\{ 0,1\}$. 
Dowie"s"c, "re nast"epuj"acy
j"ezyk jest regularny:
\[   \{ w \, : \, w\in L \wedge 
\mbox{ spo"sr"od s"l"ow o dlugo"sci $|w|$, 
 $w$ jest najmniejsze w porz"adku leksykograficznym} \} \]
\item 
%%(*) 
Przyjmujemy, "re ka"rde niepuste s"lowo binarne $w \in \{ 0,1\}^* $,
$w = w_1 \ldots w_k $, reprezentuje pewien u"lamek w przedziale $[0,1)$,
\[ \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"s"c, "re j"ezyk $L_r$ jest regularny wtedy i tylko wtedy, gdy
liczba $r$ jest wymierna.

\item Poda"c przyk"lad niesko"nczonego j"ezyka zamkni"etego na branie pods"l"ow, kt"ory nie 
zawiera niesko"nczonego j"ezyka regularnego.

\item Niech $L$ b"edzie j"ezykiem regularnym. Dowie"s"c, "re nast"epuj"ace
j"ezyki s"a r"ownie"r regularne:
\begin{itemize}
\item $\frac{1}{2}L =_{df} \{ w\, :\, (\exists u)\, |u| = |w| \wedge wu 
\in L\} $
\item $\sqrt{L} =_{df} \{ w\, : \, ww \in L\} $
\end{itemize}
\item 
%%(*) 
Niech $L$ b"edzie j"ezykiem regularnym. Dowie"s"c, "re
nast"epuj"ace j"ezyki s"a r"ownie"r regularne:
\begin{description}
\item[(a)] $\mbox{Root}(L) = \{ w\, :\, (\exists n\in N)\, w^n \in L\} $
\item[(b)] $\mbox{Sqrt}(L) = \{ w\, :\, (\exists u) |u| = |w|^2 \wedge
wu \in L \}$\\
Wskaz"owka. $n^2 = 1 + 3 + \ldots (2n-1) $.
\item[(c)] $\mbox{Log}(L) = \{ w\, :\, (\exists u) |u| = 2^{|w|} \wedge
wu \in L \}$\\
Wskaz"owka. $2^n = 1 + 2 + 2^2 + 2^{n-1} + 1$.
\item[(d)] $\mbox{Fibb}(L) = 
\{  w\, :\, (\exists u) |u| = F_{|w|} \wedge wu \in L\} $\\
gdzie $F_n$ jest $n$-t"a liczb"a Fibonacciego   tzn.
\begin{quote}
$   F_1 = F_2 = 1 $\\   
$   F_{n+2} = F_n + F_{n+1} $
\end{quote}
\end{description}


\item Dowie"s"c, "re dla dowolnego j"ezyka regularnego $L$, 
regularny jest r"ownie"r
j"ezyk
\[ \{ w\, : \, w^{|w|} \in L \} . \]
%%%%jest r"ownie"r regularny.


\item Niech b"edzie dany j"ezyk regularny
$L$ i dowolne, niekoniecznie regularne, j"ezyki
$L_1$, \ldots , $L_m$. Skonstruowa"c sko"nczony automat deterministyczny
rozpoznaj"acy j"ezyk nad alfabetem $\{ 1, \ldots ,m\}$
\[ L \, = \, \{ i_1 i_2 \ldots i_k : L_{i_1} L_{i_2} \ldots L_{i_k} \subseteq 
L \} \]




\item {\em Nietrywialnym palindromem} nazwiemy ka"rdy palindrom
o d"lugo"sci co najmniej 2.
Niech $\Pal_{\Sigma}$ oznacza zbi"or nietrywialnych palindrom"ow 
%%%%%o d"lugo"sci co najmniej 2 
nad alfabetem $\Sigma $. 
Dowie"s"c, "re j"ezyk $(\Pal_{\Sigma})^*$ 
%nie jest regularny wtedy i tylko wtedy, gdy $|\Sigma | \geq 3 $.
jest regularny wtedy i tylko wtedy, gdy $|\Sigma | = 1 $.

Czy j"ezyk $( \{ w w^R : w \in (0+1)^* \} )^* $ jest  regularny?

\item Kt"ore z nast"epuj"acych j"ezyk"ow nad alfabetem $\{ 0,1\}$
s"a regularne?
\begin{enumerate}
\item Zbi"or s"l"ow posiadaj"acych nietrywialny palindrom jako prefiks.
\item Zbi"or s"l"ow posiadaj"acych  palindrom d"lugo"sci
parzystej jako prefiks.
\item Zbi"or s"l"ow posiadaj"acych nietrywialny palindrom 
d"lugo"sci nieparzystej jako prefiks.
\end{enumerate}


\item Oznaczmy przez $\mathit{Ile}(w,x)$ liczb"e wyst"apie"n s"lowa $w$ jako pods"lowo  
$x$ (wyst"apienia nie
musz"a by"c roz"l"aczne). Czy nast"epuj"acy j"ezyk  nad alfabetem $\{a,b\}$ 
jest regularny? Je"sli tak, to
poda"c wyra"renie regularne. Je"sli nie, to udowodni"c, "re nie jest.
\begin{enumerate}
\item 
$L_1 = \{x\ :\ \mathit{Ile}(ab,x)=\mathit{Ile}(ba,x)+1 \}$
\item 
$L_2 = \{x\ :\ \mathit{Ile}(aba,x)= \mathit{Ile}(bab,x) \}$ 
\end{enumerate}

\item Niech $L$ b"edzie j"ezykiem regularnym. Dowie"s"c, "re
j"ezyki:
\begin{itemize}
\item $L_{+--} = \{ w\, :\, (\exists u)\, |u| = 2 |w| \wedge wu 
\in L\} $
\item $L_{++-} = \{ w\, : (\exists u)\, 2 |u| =  |w| \wedge wu 
\in L \} $
\item $L_{-+-} = \{ w\, : (\exists u,v)\,  |u| = |v| = |w| \wedge uwv 
\in L \} $
\end{itemize}
s"a j"ezykami regularnymi, a j"ezyk
\begin{itemize}
\item $L_{+-+} = \{ uv\, : (\exists w)\,  |u| = |v| = |w| \wedge uwv 
\in L \} $
\end{itemize}
mo"re nie by"c  regularny.


\item
Czy zachodzi fakt:\ je"sli $L$ jest regularny to istnieja dwa niepuste
s"lowa $u,v$ takie, "re zachodzi równość ilorazów 
$L \{ uv\}^{-1} =L \{ vu\}^{-1}$ ?

\item Podać przykład języka nieregularnego $L$, takiego że $L^2 $
jest językiem regularnym.

\item \label{Hamming}
Dla s"l"ow $u, v$ o tej samej d"lugo"sci, określamy odległość Hamminga 
\[ 
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 \ \}
\]

\item Przeplotem s"l"ow $w$ i $v$ nazwiemy dowolne s"lowo d"lugo"sci
$|w| + |v|$, kt"ore mo"rna rozbi"c na roz"l"aczne podci"agi $w$ i $v$.
Na przyk"lad, przeplotami s"l"ow $ab$ i $acb$ s"a s"lowa
$abacb$, $aabcb$, $acabb$, $acbab$, $aacbb$. Przeplotem j"ezyk"ow
$L$ i $M$ jest zbi"or wszystkich mo"rliwych przeplot"ow
s"l"ow $w \in L$, $v \in M$. J"ezyk ten oznaczamy $L \parallel M$.

Dowie"s"c, "re je"sli $L$ i $M$ s"a j"ezykami regularnymi, to
$L \parallel M$ jest r"ownie"r regularny. 

\item Okre"slamy $L^{\sharp } = L \, \cup \, (L \parallel L) \, \cup
\, (L \parallel L  \parallel L) \, \cup \ldots $. Poda"c przyk"lad 
j"ezyka regularnego $L$ nad dwuelementowym alfabetem, dla kt"orego
$L^{\sharp }$ nie jest j"ezykiem regularnym.




%\item Zaprojektowa"c algorytm, kt"ory dla danych automat"ow 
%deterministycznych $A, B$, rozstrzyga, czy $L(A) = L(B)$.
%\item Niech $A$ b"edzie ustalonym automatem deterministycznym.
%Zaprojektowa"c algorytm, kt"ory dla danej liczby $n$ oblicza ilo"s"c s"l"ow
%d"lugo"sci $n$ akceptowanych przez $A$.
\end{enumerate}
\subsection{Automaty minimalne.} \label{auto-mini}
\begin{enumerate}
\item \label{auto-mini-wzorce}
Niech $w \in \Sigma^*$ b"edzie s"lowem o d"lugo"sci
$|w| = n > 0$. Dowie"s"c, "re minimalny automat deterministyczny
rozpoznaj"acy 
%%j"ezyk 
wszystkie s"lowa nad $\Sigma$, 
kt"orych sufiksem jest $w$,
%%kt"ore zawieraj"a $w$ jako pods"lowo, 
ma dok"ladnie $n+1$ stan"ow.
\item
Niech $w \in \Sigma^*$ b"edzie s"lowem o d"lugo"sci
$|w| = n > 0$. Dowie"s"c, "re minimalny automat deterministyczny
rozpoznaj"acy wszystkie pods"lowa s"lowa $w$ ma nie wi"ecej
ni"r $2n$ stan"ow. 

\item
Narysowa"c diagramy automatów minimalnych rozpoznających odpowiednio
\begin{enumerate}
\item  wszystkie podsłowa
\item  wszystkie sufiksy
\end{enumerate}
słowa
$abbababa$ (dla przejrzystości rysunków pominąć stan ,,śmietnik''). 

Ile stan"ow maja  analogiczne  automaty dla $w_n = ab(ba)^n$ (licz"ac  stan ,,"smietnik'')~?

\item Skonstruowa"c minimalny deterministyczny  automat sko"nczony dla j"ezyka\vskip 0.3cm
 $L\ =\ \{a^ibb^*a^j\ :\ 2\ | \
(i+j)\}$.

\item Skonstruowa"c minimalny deterministyczny  automat sko"nczony dla j"ezyka
 $$L\ =\ \{\ a_1a_2\ldots a_n \ :\ n>0,\  a_i \in \{0,1,2,3,4\},\ MAX_{i,j}(a_i-a_j)\le 2 
 \} .$$

\item Opisa"c struktur"e  i narysowa"c diagram minimalnego  deterministycznego automatu sko"nczonego
akceptuj"acego wszystkie sko"nczone ci"agi zerojedynkowe takie, "re ka"rde $k$ kolejnych symboli zawiera
dok"ladnie  2 jedynki i ka"rde kolejnych $j<k$ symboli zawiera co najwy"rej dwie jedynki:

\begin{enumerate}
\item Dla $k=3$;
\item dla $k=4$.
\end{enumerate}

(W szczeg"olno"sci s"lowo puste  nale"ry do obu
j"ezyk"ow, a s"lowo 111 do "radnego z nich.)

\item \label{automacik}
Dowie"s"c, "re minimalny automat deterministyczny r"ownowa"rny
podanemu automatowi niedeterministycznemu o $n$ stanach ($n \geq 2 $) ma dokładnie 
\begin{enumerate}
\item \label{latwy}
\[
\xymatrix{
\ar @{=>} [r] & \circ \ar@(l,u)[]^{a,b} \ar[r]^a &  \circ  \ar[r]^{a,b} &
 \circ  \ar[r]^{a,b} &  \circ  \ar[r]^{a,b} &
 \circ  \ar[r]^{a,b} &  \circ  \ar[r]^{a,b} &
\bullet 
%%%\\ \ar @{=>} [ru] & & & & & & &
} 
\]
$2^{n-1} $ stan"ow,
\item \label{trudny} (*)
\[
\xymatrix{
\ar @{=>} [r] & \bullet \ar@(l,u)[]^{a} \ar[r]_a &  \circ \ar@(l,u)[]^{b} \ar[r]_a &
 \circ \ar@(l,u)[]^{b} \ar[r]_a & \circ \ar@(l,u)[]^{b} \ar[r]_a &
 \circ \ar@(l,u)[]^{b} \ar[r]_a & \circ \ar@(l,u)[]^{b} \ar[r]_a &
 \circ \ar@(l,u)[]^{b}
\ar @/^3pc/ [llllll]_a
} 
\]
$2^n$  stan"ow.
\end{enumerate}
Na powy"rszych rysunkach $n = 7 $, stan pocz"atkowy  jest wskazany przez
$\Rightarrow $, a stan akceptuj"acy jest oznaczony przez $\bullet $.

{\em Uwaga.\/} W"lano"s"c s"l"ow rozpoznawan"a przez automat z punktu~\ref{latwy}
mo"rna "latwo opisa"c w j"ezyku polskim, w przypadku punktu ~\ref{trudny}
jest to trudniejsze.

\item Oznaczmy przez $\Sigma_k$ alfabet $\{0,1,\ldots k\}$.\
     Niech $\mathit{NPAL}_k$ oznacza zbi"or s"l"ow nad alfabetem
    $\Sigma_k$ nie zawieraj"acych, jako pods"lowa, palindromu 
    (symetrycznego s"lowa d"lugo"sci co najmniej 2).
Ile stan"ow ma minimalny automat deterministyczny akceptuj"acy  $\mathit{NPAL}_{99}$~?
Podać rozwiązanie ogólne dla $k = 0,1,2,\ldots  $

\item Trzy dru"ryny pi"lkarskie $A$,  $B$  i $C$ rozgrywaj"a mi"edzy 
sob"a seri"e spotka"n towarzyskich, przy czym  um"owi"ly si"e, 
"re ka"rdy 
kolejny
mecz jest rozgrywany pomi"edzy dru"ryn"a, kt"ora wygra"la 
poprzedni mecz i dru"ryn"e, kt"ora nie bra"la udzia"lu w tym 
spotkaniu
(tzn.\ je"sli dru"ryna $X$ wygra"la z dru"ryn"a $Y$, to nast"epny mecz
rozegraj"a $X$ i $Z$).
 Zak"ladaj"ac, "re 
{\em  nie ma remis"ow},
rozwa"ramy zbi"or s"l"ow nad alfabetem $\{ A,B,C \}$,
stanowi"acych ci"agi mo"rliwych wynik"ow spotka"n. Dowie"s"c, "re jest
to j"ezyk regularny. Zbudowa"c minimalny automat deterministyczny, kt"ory
go rozpoznaje. 
\item Pan $X$ zakupi"l  pakiety trzech r"o"rnych akcji: $A,B$ i $C$.
Ka"rdego dnia  bada wzajemne po"lo"renie warto"sci swoich akcji, 
kt"ore mo"re by"c reprezentowane jako {\em uporz"adkowanie} zbioru
$\{ A,B,C\}$, w kierunku od najmniej do najbardziej warto"sciowej. 
(Przyjmujemy  za"lo"renie, "re dwie r"o"rne akcje maj"a zawsze
{\em r"o"rne} warto"sci.)
Pan $X$ postanowi"l, "re je"sli w ci"agu dw"och kolejnych dni kt"ora"s
z akcji dwukrotnie spadnie na ni"rsz"a pozycj"e, to sprzeda t"e akcj"e.
Np. je"sli kolejne notowania (w tym wypadku: uporz"adkowania) s"a 
$(A,B,C),(B,C,A), (C,B,A)$ to pan $X$
sprzeda pakiet akcji $C$.
Rozwa"ramy zbi"or $G$ wszystkich uporz"adkowa"n
liniowych 
zbioru $\{ A,B,C\}$. 
Dowie"s"c, "re zbi"or tych ci"ag"ow nad alfabetem $G$,
%notowa"n gie"ldowych, 
kt"ore opisuj"a takie wyniki notowa"n gie"ldowych,
przy kt"orych pan $X$ nie pozb"edzie si"e "radnego
pakietu akcji, jest j"ezykiem regularnym. Znale"z"c liczb"e stan"ow
automatu minimalnego akceptuj"acego ten j"ezyk.
\item Pan $X$ postanowi"l, "re ka"rdego dnia b"edzie pracowa"l lub nie,
przestrzegaj"ac przy tym  zasady, by  na "radne siedem kolejnych dni nie
przypada"lo wi"ecej ni"r cztery dni pracy. Mo"rliwy rozk"lad dni pracy
pana $X$ w ci"agu $n$ kolejnych dni mo"remy przedstawi"c 
jako $n$-bitowe s"lowo,
gdzie 1 odpowiada dniowi pracy, a 0 dniowi odpoczynku. Dowie"s"c, "re
zbi"or wszystkich tak otrzymanych s"l"ow jest j"ezykiem regularnym
(nad alfabetem $\{ 0,1\}$). Znale"z"c minimalny automat deterministyczny.

\item Dowie"s"c, "re istnieje niesko"nczenie wiele s"l"ow
$w \in (a+b)^*$ takich, "re je"sli zastosujemy homomorfizm
$a \mapsto 0$, $b \mapsto 1$, to otrzymamy zapis binarny liczby
podzielnej przez 3, a kiedy zastosujemy homomorfizm
$a \mapsto 1$, $b \mapsto 0$, to r"ownie"r
otrzymamy zapis binarny liczby podzielnej przez 3
(oczywi"scie ignorujemy pocz"atkowe zera).

%\item Dowie"s"c, "re istnieje niesko"nczenie wiele liczb $n$ takich,


%Ile stan"ow ma minimalny automat deterministyczny rozpoznaj"acy
%ten j"ezyk~?

\item 
Rozwa"ramy automat wydaj"acy napoje, dzia"laj"acy na nast"epuj"acych zasadach.

--- Ka"rdy nap"oj kosztuje 1 z"loty. 

--- W chwili pocz"atkowej automat nie zawiera "radnych monet.

--- Automat przyjmuje monety:  1 z"loty lub 1 euro; w tym ostatnim przypadku
wydaje 3 z"lote reszty  po warunkiem, oczywi"scie, "re ma dostateczn"a ilo"s"c
monet
jednoz"lotowych
(zak"ladamy, "re \euro{1} = 4 z"l).

--- Je"sli automat nie jest w stanie wyda"c reszty --- sygnalizuje 
{\bf b"l"ad\/}.

--- Je"sli po wrzuceniu monety i ewentualnym wydaniu reszty
warto"s"c wszystkich  monet zgromadzonych w automacie
osi"agnie  r"ownowarto"s"c  8 z"l,
%%%%(przy czym nie wyst"api"l  b"l"ad),
wszystkie monety s"a wyjmowane  ({\em reset}).


Histori"a dzia"lania jest ci"ag wrzuconych monet (z"loty lub euro).
   Historia jest {\em udana\/}, je"sli w trakcie jej realizacji
   ani razu nie wyst"api"l b"l"ad.

Skonstruowa"c  minimalny automat deterministyczny rozpoznajacy zbi"or
wszystkich udanych historii.



%\end{enumerate}
\end{enumerate}
\subsection{Rozpoznawanie wzorca w tek"scie}
\label{wzorce}
\begin{enumerate}
\item \label{auto-wzorce-wstecz}
Deterministyczny automat z zadania~\ref{auto-mini-wzorce}
z punktu~\ref{auto-mini} rozpoznaj"acy
j"ezyk $\Sigma^* w  $ mo"rna skonstruowa"c bior"ac za stany
wszystkie prefiksy s"lowa $w$ (a zatem $|w| + 1$ stan"ow)
oraz przej"scia $v \stackrel{a}{\rightarrow} u $, gdzie $u$ jest
maksymalnym sufiksem s"lowa $v a$ b"ed"acym jednocze"snie
prefiksem $w$. (Efektywna konstrukcja tego"r automatu,
patrz zadanie~\ref{auto-wzorce-algo} w punkcie~\ref{algorytmy}.)
Dowie"s"c, "re liczba nietrywialnych przej"s"c ,,wstecznych'',
tj.~przej"s"c postaci $v \stackrel{a}{\rightarrow} u $, gdzie
$ |v| > |u| > 0$,
%%%%$0 < |u| < |v|$, 
jest nie wi"eksza ni"r $|w|$.
Zauwa"rmy, "re daje to mo"rliwo"s"c  reprezentacji automatu 
%%liniowej
o rozmiarze 
%%liniowym wzgl"edem 
proporcjonalnym do
$|w|$
%%, ale niezale"rnej od rozmiaru alfabetu
(przej"scia postaci $v \stackrel{a}{\rightarrow} \epsilon $ mo"remy
pomin"a"c).

{\em Wskaz"owka.\/} 
Wykaza"c, "re dla ka"rdej liczby $k$ istnieje co najwy"rej jedno
nietrywialne przej"scie wsteczne, takie, "re $ |v a| - |u | = k$.
%Zauwa"ry"c, "re je"sli $v_1$ i $v_2$ s"a 
%(r"o"rnymi) prefiksami s"lowa $w$ takimi, kt"ore mo"rna
%niezerowo ,,przesun"a"c w prawo'', w ten spos"ob, "re 
%%%%%%dla pewnych niezerowych $x$ i $y$, $x v_1$ i $y v_2$ s"a r"ownie"r 
%%prefiksami s"lowa $w$, to $ |x| \neq |y| $.

\item {\em Rozpoznawanie pods"l"ow.\/} 
\begin{enumerate}
%%\item
\item Dla danego s"lowa $w$ 
o d"lugo"sci $|w| = n$
skonstruowa"c automat deterministyczny o $\leq 2 n + 1$ stanach
rozpoznaj"acy dok"ladnie zbi"or sufiks"ow s"lowa $w$.

{\em Wskaz"owka.\/}  Jako stany automatu mo"rna wzi"a"c zbiory
pozycji
$S_x$ ($S_x \subseteq \{ 0,1, \ldots ,n\}$) ko"ncz"acych wyst"apienie
$x$ jako pods"lowa  s"lowa $w$. Oszacowanie na liczb"e stan"ow wynika ze
spostrze"renia,
"re r"o"rne zbiory $S_x$, $S_y$ s"a albo w relacji inkluzji albo
roz"l"aczne, a zatem, ze wzgl"edu na inkluzj"e, tworz"a drzewo
o nie wi"ecej ni"r $n$ li"sciach.
\item Powy"rszy automat zawiera stan typu ,,czarna dziura'', mianowicie stan
$\emptyset = S_x$, gdzie $x$ nie jest pods"lowem $w$. Dowie"s"c, "re 
liczb"e  przej"s"c nie prowadz"acych do stanu $\emptyset $ mo"rna
oszacowa"c z g"ory przez $3 n$.

{\em Wskaz"owka.\/} Wzi"a"c drzewo rozpinaj"ace grafu automatu i oszacowa"c
liczb"e pozosta"lych kraw"edzi przez liczb"e sufiks"ow $w$.
\item Opisany wy"rej automat jest minimalny dla zbioru sufiks"ow.
T"e sam"a konstrukcj"e
mo"rna  zastosowa"c r"ownie"r do rozpoznawania zbioru wszystkich
pods"l"ow s"lowa $w$, ale otrzymany automat nie musi by"c minimalny.
Poda"c przyk"lad.

{\em Wskaz"owka:\/} 4 grudnia.

\end{enumerate}

\end{enumerate}

\subsection{Warianty automat"ow sko"nczonych} \label{sect:variant}
\begin{enumerate}
\item \label{exo:epsilon}
{\em Automaty z $\epsilon $-przej"sciami.} 
Niedeterministyczny automat z $\epsilon $-przej"sciami
$A = ( \Sigma , Q, I, \delta , F )$ jest okre"slony jak zwyk"ly
automat sko"nczony z tym, "re
$\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"slona jak poprzednio, tzn.~$q \stackrel{\epsilon }{\rightarrow} q$
i $q \stackrel{v a}{\rightarrow} p $ o ile $q \stackrel{v }{\rightarrow} q_1$
i $(q_1,a,p) \in \delta$ z tym, "re teraz $a$ mo"re by"c liter"a
w $\Sigma $ lub $\epsilon $. 

Dowie"s"c, "re dla dowolnego automatu z $\epsilon $-przej"sciami
istnieje zwyk"ly automat sko"nczony, kt"ory akceptuje ten sam j"ezyk.

\item  {\em Automat z wyj"sciem wg Mealy'ego.}
Automat Mealy'ego mo"rna przedstawi"c jako 
deterministyczny automata
sko"nczony, powiedzmy $A = ( \Sigma , Q, q_I, \delta , F )$  dany
razem z funkcj"a $\gamma : Q \times \Sigma \to \Delta $.
Intuicyjnie, dany stan $q$ i litera $\sigma \in \Sigma $ determinuj"a
nie tylko kolejny stan, powiedzmy $p$, ale tak"re sygna"l
wyj"sciowy ({\em output\/}),  $\gamma (q,\sigma )$.
Dok"ladniej, s"lowo $w = w_1 w_2 \ldots w_n$ nad $\Sigma $,
takie, "re $\hat{\delta } (q_I, w_1 \ldots w_{i-1} ) = p_i$, dla
$i = 1,\ldots ,n$,
 wyznacza $n$-literowe
s"lowo nad alfabetem $\Delta $,
\[
\hat{\gamma }(w) =_{def} \gamma ( q_I ,w_1)  \gamma (p_2,w_2) \ldots 
 \gamma (p_n ,w_n )
\]
Powiemy, "re automat Mealy'ego redukuje j"ezyk $L_1$ do $L_2$ je"sli
($\forall w $)  $w \in L_1 \Leftrightarrow \hat{\gamma }(w) \in L_2 $.
Skonstruowa"c automat, kt"ory redukuje $a^* b (a^* b a^* b a^* )^* $ do
$(a^* b a^* b a^* )^*$.
\item  {\em Automat z wyj"sciem wg Moore'a.} Automat Moore'a
 mo"rna przedstawi"c jako 
deterministyczny automata
sko"nczony wraz z funkcj"a $\gamma : Q \to \Delta $.
Tym razem, s"lowo $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"s"c, "re automaty Mealy'ego i Moore'a s"a r"ownowa"rne
w tym sensie, "re dla ka"rdego automatu jednego typu mo"rna
znale"z"c automat drugiego typu realizuj"acy t"e sam"a funkcj"e
$\hat{\gamma }$.

\item {\em Automaty dwukierunkowe.} Funkcja przej"scia deterministycznego
automatu dwukierunkowego jest postaci $\delta : Q\times \Sigma \to
Q \times \{ L,R\}$, co interpretujemy, "re automat mo"re przesun"a"c
czytnik zar"owno w prawo jak i w lewo.
Dowie"s"c, "re deterministyczne automaty dwukierunkowe mog"a
by"c symulowane przez zwyk"le automaty sko"nczone.
(Rezultat zachodzi r"ownie"r dla automat"ow niedeterministycznych.)

{\em Wskaz"owka.}  Znane rozwi"azanie oparte na idei ci"ag"ow
skrzy"rowa"n (ang.~{\em crossing sequences\/}) mo"rna
znale"z"c w rozdziale 2.6 ksi"a"rki
J.E.Hopcroft, J.D.Ullman, {\em Wprowadzenie do teorii automat"ow,
j"ezyk"ow i oblicze"n}, Wydaw\-nictwo Naukowe PWN, Warszawa 1994.
Innym, by"c mo"re prostszym rozwi"azaniem\footnote{Zaproponowanym
przez Miko"laja Boja"nczyka.} jest uwzgl"ednienie w stanie
symuluj"acego  automatu
jednokierunkowego  funkcji $h : Q \to Q \cup \{ \bot \} $
o nast"epuj"acej interpretacji: je"sli automat (dwukierunkowy) 
p"ojdzie w lewo w stanie $q$, to wr"oci w stanie $h(q)$
(by"c mo"re wcale nie wr"oci, gdy $h(q) = \bot $).


{\em Uwaga.} W dalszej cz"e"sci wyk"ladu spotkamy si"e
z mocniejszym stwierdzeniem,
a mianowicie, "re maszyny Turinga pracuj"ace na jednej ta"smie
w czasie liniowym  akceptuj"a jedynie j"ezyki regularne.



\end{enumerate}


\subsection{Algorytmy i z"lo"rono"s"c} \label{algorytmy}
\begin{enumerate}
\item \label{algo wyrazenie}
Zaprojektowa"c algorytm, kt"ory
dla wyra"renia regularnego $\beta $ i s"lowa $w \in \Sigma^*$ 
odpowiada na pytanie,
czy $w$ nale"ry do j"ezyka opisywanego przez $\beta $
\begin{enumerate}
\item w czasie ${\cal O} ( |\Sigma | \cdot |\beta |^2 \cdot |w| )$,
\item \label{lepiej} w czasie ${\cal O} (  |\beta | \cdot |w| )$,
\end{enumerate}
{\em Wskaz"owka.\/} Skonstruowa"c automat niedeterministyczny r"ownowa"rny
wyra"reniu $\beta $ i obliczy"c zbi"or stan"ow osi"agalnych po s"lowie
$w$. Dla oszacowania w punkcie~\ref{lepiej} u"ry"c automatu
z $\epsilon $-przej"sciami
(por.~zadanie~\ref{sect:variant}.~\ref{exo:epsilon}), 
w grafie kt"orego z ka"rdego stanu wychodz"a co
najwy"rej dwie kraw"edzie.
\item 
Rozwa"ramy pytanie ,,$w \in L [\beta ]$~?'' jak w 
zadaniu~\ref{algo wyrazenie}, ale dla {\em uog"olnionego\/} wyra"renia
regularnego, tj.~takiego, w kt"orym dopuszczamy r"ownie"r operacje
teorio--mnogo"sciowe $\cap $ i $-$. Zaprojektowa"c algorytm, kt"ory 
rozstrzyga to pytanie w czasie wielomianowym od $|\beta | + |w|$.

{\em Wskaz"owka.\/} Zastosowa"c metod"e programowania dynamicznego:
dla $1 \leq i \leq j \leq |w|$ sukcesywnie oblicza"c zbi"or podwyra"re"n
$\alpha $ wyra"renia $\beta $ takich, "re $w [i .. j] \in L [\alpha ]$.

\item \label{auto-wzorce-algo}
Konstrukcj"e automatu z 
zada"n~\ref{auto-mini}.~\ref{auto-mini-wzorce} 
i~\ref{wzorce}.~\ref{auto-wzorce-wstecz}, 
kt"ory dla danego $w$ rozpoznaje j"ezyk $\Sigma^* w$, mo"rna przeprowadzi"c
za pomoc"a nast"epuj"acego algorytmu. Niech $m = |w|$. 

Najpierw obliczamy pomocnicz"a tablic"e $F [ 0..m ]$, tak"a, "re
$F [0] = 0$ oraz $F [i] $ jest d"lugo"sci"a najd"lu"rszego prefiksu
w"la"sciwego $w [ 1 .. i ]$ b"ed"acego jednocze"snie sufiksem $w [1..i]$,
dla $i = 1, \ldots ,m$.

%%\noindent
$F [0] := F [1] := 0$;  $i := 0$;

\underline{for} $j:= 2$ \underline{to} $m$ \underline{do}

\underline{begin}  $(* \, i = F [j-1] \, *)$

\hspace{9pt} 
\underline{while} $w_j \neq w_{i+1}$ $\wedge $
$i > 0$ \underline{do} $i:= F[i] $;

\hspace{9pt}
\underline{if} $w_j = w_{i+1}$ \underline{then} $i:=i+1$;

\hspace{9pt}
$F[j] := i $

\underline{end}

W konstrukcji automatu przyjmujemy, "re stany s"a liczbami
%%%%wygodnie jest przedstawi"c stany jako liczby 
$0,1, \ldots , m$ (kt"ore
mo"rna uto"rsami"c z prefiksami $w$ o odpowiednich d"lugo"sciach).
Funkcj"e przej"scia $\delta $ okre"slamy przez
\begin{itemize}
\item $\delta (0,w_1 ) = 1$,  $\delta (0,a) = 0$, dla $a \neq w_1$, 
\item 
$\delta (j, w_{j+1} ) = j+1$,  $\delta (j, a) =
\delta (F[j] ,a)$, dla $a \neq w_{j+1}$
\end{itemize}
Dowie"s"c, "re powy"rszy algorytm oblicza "r"adany automat w czasie
liniowym wzgl"edem d"lugo"sci $w$ (zale"rnym od alafabetu).

\item Niech $A$ b"edzie ustalonym automatem deterministycznym.
Zaprojektowa"c algorytm, kt"ory dla danej liczby $n$ znajduje
w czasie ${\cal O} (n)$
%%liniowym wzgl"edem $n$
%% ilo"s"c 
liczb"e s"l"ow
d"lugo"sci $n$ akceptowanych przez $A$.

\item Poda"c przyk"lad "swiadcz"acy o tym, "re najkr"otsze s"lowo, jakiego
nie akceptuje automat niedeterministyczny o $n$ stanach mo"re mie"c
d"lugo"s"c $2^{\Omega (n) }$.

{\em Wskaz"owka.\/} Rozwa"ry"c automat akceptuj"acy wszystko za wyj"atkiem
s"lowa 
$$(\ldots ((a_0^2 a_1 )^2 a_2)^2 a_3 \ldots  a_{n-1})^2 a_n .$$

\item \label{min rozne}
Dowie"s"c, "re je"sli dwa stany $n$--stanowego automatu 
deterministycznego nie s"a r"ownowa"rne (tzn.~$L(A,q) \neq L(A,p)$),
to istnieje s"lowo d"lugo"sci nie wi"ekszej ni"r $n$ akceptowane
z dok"ladnie jednego z nich.

{\em Wskaz"owka.\/} Rozwa"ry"c zst"epuj"acy ci"ag relacji r"ownowa"rno"sci
na zbiorze stan"ow: $R_i (p,q) $ o ile stany $p$ i $q$ s"a nierozr"o"rnialne
s"lowami d"lugo"sci $\leq i$.

\item Poda"c algorytm rozstrzygaj"acy r"ownowa"rno"s"c dw"och automat"ow
deterministycznych.

{\em Uwaga.\/} Zastosowanie idei zadania~\ref{min rozne} prowadzi
do efektywniejszego algorytmu ni"r testowanie niepusto"sci automatu
produktowego.

\item  Czy dla s"l"ow $u,v$ takich, "re $|u|<|v|=n$ istnieje
automat deterministyczny spe"lniaj"acy:\ 
$u\in L(A)\ \wedge  v\notin L(A)$
i maj"acy ${\cal O}(\log n)$ stan"ow?
%%%% is pe"lniaj"acy:\ 
%%%$u\in L(A)\ \& v\notin L(A)$.

\item 
\begin{enumerate}
\item Wykaza"c, "re dla dowolnego
automatu niedeterministycznego o $n$ stanach
mo"rna skonstruowa"c r"ownowa"rne wyra"renie regularne d"lugo"sci
$2^{{\cal O} (n)}$.
\item (**)
Poda"c przyk"lad "swiadcz"acy o tym, "re najkr"otsze 
wyra"renie regularne r"ownowa"rne danemu automatowi deterministycznemu
o $n$ stanach mo"re mie"c d"lugo"s"c
$2^{\Omega (n) }$.

{\em Wskaz"owka.\/} Rozwa"ry"c automat, kt"orego graf jest pe"lnym grafem
o $n$ wierzcho"lkach, a ka"rda kraw"ed"z ma inn"a etykiet"e. 
Stosuj"ac indukcj"e po $n$, skonstruowa"c p"etl"e, kt"ora
,,wymusza'' eksponencjaln"a d"lugo"s"c wyra"renia regularnego.
%Dowie"s"c, "re istnieje p"etla taka, "re ka"rde wyra"renie, kt"ore j"a pokrywa
%%ma d"lugo"s"c co najmniej $2^{n-1}$. Zastosowa"c indukcj"e po $n$.
\end{enumerate}


\item {\em Eksplozja stan"ow w produkcie automat"ow.}
Niech $\Sigma = \{ 0,1, \ldots ,k\}$ i niech dla $i = 1, \ldots ,k$,
$L_i$ b"edzie zbiorem s"l"ow $v$ nad $\Sigma$ o nast"epuj"acej w"lasno"sci:
\begin{quote}
$i$ wyst"epuje w $v$, ale przed pierwszym i pomi"edzy ka"zdymi dwoma
kolejnymi wyst"apieniami $i$, $i-1$ wyst"epuje co najmniej dwa razy.
\end{quote}
Nietrudno jest skonstruowa"c  deterministyczny  automat o 4 stanach
rozpoznaj"acy $L_i$. 
%%
Dowie"s"c, "re ka"rdy 
(nawet niedeterministyczny) automat rozpoznaj"acy j"ezyk
$L_1 \cap \ldots  \cap L_k$ musi mie"c co najmniej $2^{k+1} - 1$ stan"ow.

{\em Wskaz"owka.\/} Oszacowa"c od do"lu d"lugo"s"c najkr"otszego s"lowa
w tym j"ezyku.
%Z drugiej strony, najkr"otsze s"lowo w ma d"lugo"s"c $1+2+ \ldots +2^k$,
%a zatem ka"zdy automat rozpoznaj"acy ten j"ezyk musi mie"c
%co najmniej tyle"z stan"ow (dlaczego?).

\item Dowie"s"c, "re jakikolwiek automat niedeterministyczny
rozpoznaj"acy j"ezyk $\{ x c y :
\, x,y \in \{ a,b \}^* \, \wedge \, x[1..k] = y[1..k] \}$ ma
$2^{\Omega (k ) }$ stan"ow.

\item Zakładając, "re następujący automat deterministyczny $A_n $ ma $n$ stanów
($n \geq 2 $, na rysunku $n= 6$), dowieść, "re jakikolwiek automat
{\em deterministyczny\/} rozpoznający lustrzane odbicie języka $L (A_n) $ ma
co najmniej $2^n $ stanów (por.\ zadanie~\ref{automacik} na str.~\pageref{automacik}).

\[
\xymatrix{
\Rightarrow  \bullet \ar  @/^1pc/  [r]^{b,c} \ar @/_3pc/ [rrrrr]^a & 
\circ \ar@(r,u)[]_{b} \ar   [l]^{a,c}   & \circ \ar[l]^a \ar@(r,u)[]_{b,c} &
\circ \ar[l]^a \ar@(r,u)[]_{b,c} & \circ \ar[l]^a \ar@(r,u)[]_{b,c} & \circ \ar[l]^a \ar@(r,u)[]_{b,c} 
} 
\]

\item {\em S"lowo synchronizuj"ace.} M"owimy, "re
s"lowo $w$ synchronizuje stany automatu deterministycznego, je"sli
istnieje taki stan $q_0$, "re startuj"ac z dowolnego stanu i czytaj"ac
s"lowo $w$, automat dojdzie zawsze do stanu $q_0$, tzn. 
$ (\forall q \in Q)\,
q \stackrel{w}{\rightarrow } q_0
$.

\begin{enumerate}
\item \label{biegacze} Znale"z"c s"lowo synchronizuj"ace dla automatu nad
alfabetem  $\{a,b\} $ o zbiorze stan"ow
$ \{ 0,1,\ldots , k-1 \}
$ i funkcji przej"scia

\begin{tabular}{l l }
 $ i \stackrel{a}{\rightarrow } i+1 \pmod{k} $ & dla $ i = 0,1, \ldots , k-1 $ \\
 $ i \stackrel{b}{\rightarrow } i  $
& dla i = 0,1, \ldots , k-2\\
$k-1  \stackrel{b}{\rightarrow } 0$  &.
 \end{tabular}

\item Zaprojektowa"c algorytm, kt"ory dla automatu o $n$ stanach rozstrzyga
w czasie
$ {\cal O} (n^3 )$, czy istnieje s"lowo synchronizuj"ace i 
w pozytywnym przypadku znajduje takie s"lowo
(d"lugo"sci $ \leq (n-1)^3$).

\item (*) Znale"z"c {\em najkr"otsze\/} s"lowo synchronizuj"ace dla automatu
z punktu (\ref{biegacze}).
\end{enumerate}

{\em Uwaga}. Licz"aca ju"r 40 lat {\em hipoteza \v{C}ernego}\footnote{Zob.
http://www.liafa.jussieu.fr/$\sim $jep/Problemes/Cerny.html.} g"losi,
"re najkr"otsze s"lowo synchronizuj"ace, o ile istnieje,
ma d"lugo"s"c $(n-1)^2$.
%%%%%%(zob.~http://www.liafa.jussieu.fr/$\sim $jep/Problemes/Cerny.html).

\item \label{drugie_kody}
Poda"c wielomianowy algorytm sprawdzania, czy dany sko"nczony zbi"or
słów $C \subseteq \Sigma^*$ jest kodem (por.\ rozdz.\ \ref{section:slowa},
zadanie \ref{kody}).

{\em Wskaz"owka.} Skonstruować automat skończony, rozpoznający hipotetyczne
słowa posiadające dwie różne faktoryzacje.


\end{enumerate}

\section{J"ezyki bezkontekstowe}
\subsection{Gramatyki bezkontekstowe} \label{sect:gramatyki}
\begin{enumerate}


\item Poda"c gramatyki bezkontekstowe generuj"ace nast"epuj"ace
j"ezyki:
\begin{enumerate}
\item zbi"or s"l"ow nad alfabetem $\{ a,b\}$, kt"ore zawieraj"a tyle
samo $a$ co $b$;
\item zbi"or s"l"ow nad alfabetem $\{ a,b\}$, kt"ore zawieraj"a dwa razy
wi"ecej $a$ ni"r $b$;
\item zbi"or s"l"ow nad alfabetem $\{ a,b\}$ o d"lugo"sci parzystej, 
w kt"orych liczba wyst"apie"n litery $b$ na pozycjach parzystych jest
r"owna liczbie wyst"apie"n tej litery  na pozycjach nieparzystych;
\item zbi"or wyra"re"n arytmetycznych nad alfabetem $\{ 0,1,(,),+,\cdot \}$,
kt"ore, przy zwyk"lej interpretacji dzia"la"n dla liczb naturalnych,
maj"a warto"s"c 3;
%o warto"sci 3;
\item zbi"or wyra"re"n arytmetycznych w notacji polskiej (nad alfabetem 
$\{ 0,1,+,\cdot \}$) o warto"sci 4;
\item zbi"or poprawnie zbudowanych formu"l rachunku zda"n ze zmienn"a
zda\-nio\-w"a $p$ i sta"lymi logicznymi {\bf true}, {\bf false} (alfabet:
$\{ p, \mbox{\bf true},\mbox{\bf false},\wedge ,\vee , \neg , (, ) \}$);
\item \label{formuly_raz} zbi"or tych formu"l z poprzedniego punktu, kt"ore 
przy ka"rdym warto"sciowaniu zmiennej $p$ maj"a 
warto"s"c logiczn"a
{\em prawda\/} (tzn.~ tautologii);
\item $\{ a^i b^j c^k \, : \, i\neq j \, \vee \, j\neq k \}$;
\item $\{ a^i b^j a^k \, : \, i + k = j \}$.
%%%%\item $\{ a,b\}^* \,- \, \{ ww\, :\, w\in \{ a,b\}^* \}$.
\end{enumerate}
\item Dla danych gramatyk bezkontekstowych $G, H$, skonstruowa"c gramatyki
generuj"ace j"ezyki $L(G) \cup L(H)$, $L(G) L(H)$, $(L(G))^* $,
$(L(G))^R $ (=lustrzane odbicie).

\item \label{palindromy i nie}
 Wykaza"c, "re zbi"or palindrom"ow nad ustalonym alfabetem
jak r"ownie"r jego dope"lnienie s"a j"ezykami bezkontekstowymi.

\item Napisa"c gramatyk"e bezkontekstow"a
(jak najkr"otsz"a) generuj"ac"a j"ezyk: 
\vskip 0.1cm \centerline{$L \ =\  \{\ a^ib^j\ :\ i,j\ge 1;\ i < 2j-1\
\}$}


\item \label{poprzednie}
Skonstruowa"c gramatyk"e bezkontekstow"a z jednym symbolem
nieterminalnym generuj"ac"a zbi"or $\{x \in (a + b)^*\ :\ \#_a(x)=
 \#_b(x) \ \}$, gdzie $\#_s(w) $ oznacza liczb"e wyst"apie"n
 symbolu $s$ w s"lowie $w$.

\item
Skonstruowa"c gramatyk"e bezkontekstow"a jednoznaczną generuj"ac"a język $\mathbf{D_1}$
poprawnie uformowanych wyrażeń nawiasowych (por.\ Rozdział~\ref{section:slowa},
Zadanie~\ref{nawiasy}).

\item Napisać gramatyki bezkontekstowe generujace zbiór tych słów z języka  $\mathbf{D_1}$,
które
\begin{enumerate}
\item zawierają parzystą liczbę (np.\ 0) nawiasów otwierających,
\item nie zawierają podsłowa (()).
\end{enumerate}

\item
Skonstruowa"c gramatyk"e bezkontekstow"a jednoznaczną generuj"ac"a język
z Zadania~\ref{poprzednie}.

{\em Wskaz"owka.\/}\footnote{Rozwiązanie podane przez studenta, pana Dariusza Leniowskiego.}
Rozważyć gramatykę
\begin{eqnarray*}
Z  & \rightarrow & Z a Z^+ b  \, | \, Z b  Z^- a \, | \, \varepsilon \\
Z^+ & \rightarrow & Z^+ a Z^+ b \, | \, \varepsilon \\
Z^- & \rightarrow & Z^- b Z^- a \, | \, \varepsilon \\
\end{eqnarray*}
Zauważyć związek miedzy produkcjami dla $Z^+  $ a poprzednim zadaniem
(podobnie dla $Z^-  $).

\item Dowie"s"c, "re nast"epuj"ace warunki s"a r"ownowa"rne dla j"ezyka
$L\subseteq \Sigma^* $:
\begin{enumerate}
\item $L$ jest regularny,
\item $L$ jest generowany przez gramatyk"e bezkontekstow"a, w kt"orej
ka"rda regu"la jest postaci $X \rightarrow \epsilon$, $X \rightarrow Y$,
lub $X \rightarrow \sigma Y$, $\sigma \in \Sigma$,
\item $L$ jest generowany przez gramatyk"e bezkontekstow"a, w kt"orej
ka"rda regu"la jest postaci $X \rightarrow \epsilon$, $X \rightarrow Y$,
lub $X \rightarrow Y \sigma $, $\sigma \in \Sigma$,
\item $L$ jest generowany przez gramatyk"e bezkontekstow"a, w kt"orej
ka"rda regu"la jest postaci $X \rightarrow \alpha $ 
lub $X \rightarrow \beta Y$, $\alpha ,\beta  \in \Sigma^*$.
\end{enumerate}
\item Poda"c przyk"lad gramatyki bezkontekstowej w kt"orej
ka"rda regu"la jest postaci $X \rightarrow \epsilon$, $X \rightarrow Y$,
$X \rightarrow \sigma Y$ lub $X \rightarrow Y \sigma $,  $\sigma \in \Sigma$,
ale j"ezyk generowany przez gramatyk"e nie jest regularny.
\item  Czy ka"rdy j"ezyk bezkontekstowy jest generowany przez gramatyk"e
w postaci z poprzedniego zadania?
\item
Powiemy, "re gramatyka $G$ ma w"lasno"s"c 
{\em w"la"sciwego samozap"etlenia\/},
je"sli dla pewnej zmiennej $X$ zachodzi 
$X \stackrel{G }{\rightarrow }^* \alpha X \beta $, gdzie
$\alpha , \beta \neq \epsilon $.
Udowodnij, "re gramatyka bezkontekstowa nie maj"aca w"lasno"sci w"la"sciwego
samozap"etlenia generuje j"ezyk regularny.



\item Udowodnij, "re ka"rdy j"ezyk bezkontekstowy nad jednoliterowym
alfabetem jest regularny.


\item
Udowodnij, "re je"sli $L$ jest bezkontekstowy to j"ezyk
$\{a^{|w|}\ :\ w \in L\}$ jest regularny.



\item Niech $G$ b"edzie gramatyk"a bezkontekstow"a, z $m$ zmiennymi i niech,
dla ka"rdej regu"ly $Y \stackrel{G }{\rightarrow } w $, $|w| \leq \ell $.
Dowie"s"c, "re je"sli $X^I \stackrel{G* }{\rightarrow } \epsilon $, to
istnieje wyprowadzenie o d"lugo"sci $1 + \ell + \ell^2 +\ldots + \ell^{m-1}$.
Czy to oszacowanie jest optymalne?
\item Dowie"s"c, "re dla ka"rdej gramatyki $G$ istnieje sta"la $C$, taka,
"re dla dowolnego $w\neq \epsilon$, je"sli 
$X_I \stackrel{G* }{\rightarrow } w $, to istnieje wyprowadzenie o d"lugo"sci
$\leq C \cdot |w|$.


\item
Za"l"o"rmy, "re mamy pewn"a sko"nczon"a liczb"e regu"l wymazuj"acych 
postaci $\alpha \rightarrow \epsilon$. 
Stosuj"ac takie regu"ly mo"remy w danym s"lowie
zast"epowa"c s"lowo $\alpha$ przez s"lowo puste.
Niech $L$ b"edzie zbiorem s"l"ow, kt"ore mo"remy przekszta"lci"c na s"lowo 
puste stosuj"ac regu"ly wymazywania.

Czy zawsze istnieje  gramatyka bezkontekstowa generuj"aca $L$ i maj"aca
tylko jeden symbol nieterminalny~?



\item Zaprojektowa"c algorytm, kt"ory, dla danej gramatyki $G$, odpowiada
na pytanie, czy j"ezyk $L(G)$ jest niesko"nczony.


\item
Udowodnij, "re ka"rdy j"ezyk bezkontekstowy mo"re by"c 
generowany przez gramatyk"e
w kt"orej ka"rdy 
symbol
nieterminalny (poza by"c mo"re symbolem pocz"atkowym)
generuje niesko"nczenie wiele s"l"ow terminalnych.


\end{enumerate}



\subsection{Bezkontekstowy czy nie? --- lematy o pompowaniu}
\begin{enumerate}

\item 
Udowodni"c, "re "raden niesko"nczony podzbi"or j"ezyka $L\ =\ 
\{a^nb^nc^n\ :\ n \ge 1\}$ nie jest j"ezykiem bezkontekstowym.
\item 
Udowodni"c, "re dope"lnienie j"ezyka z poprzedniego zadania jest
j"ezykiem bezkontekstowym.
\item Udowodni"c, "re je"sli alfabet $\Sigma $ ma co najmniej dwie
litery, to j"ezyk $L = \{ ww : w \in \Sigma^* \}$ nie jest bezkontekstowy,
natomiast jego dope"lnienie $\Sigma^* - L$ jest j"ezykiem
bezkontekstowym.
\item Dowie"s"c, "re dla ka"rdego ustalonego $k$ dope"lnienie
j"ezyka 
$\{ w^k :   w \in \Sigma^* \} $ jest j"ezykiem
bezkontekstowym.
\item 
Udowodni"c, "re  j"ezyk $L\ =\ 
\{xcx\ :\ x \in (a + b)^*\ \}$ nie jest j"ezykiem bezkontekstowym.
\item 
Udowodni"c, "re 
dope"lnienie j"ezyka z poprzedniego zadania jest
j"ezykiem bezkontekstowym.

\item Niech $\mbox{\em Subwords\/} (x) $ oznacza zbiór wszystkich podsłów
słowa $x$, 
$\mbox{\em Subwords\/} (L) = \bigcup_{x \in L} \mbox{\em Subwords\/} (x)$.
\begin{enumerate}
\item Udowodnić, że dla języka bezkontekstowego $L$, $\mbox{\em Subwords\/} (L)$
jest językiem bezkontekstowym.
\item Podać przykład języka bezkontekstowego nieregularnego $L$, dla którego
$\mbox{\em Subwords\/} (L)$ jest językiem regularnym.
\item Podać przykład języka bezkontekstowego $L$, dla którego
$\mbox{\em Subwords\/} (L)$ nie jest językiem regularnym.
\end{enumerate}
\item Pokaza"c, "re j"ezyk dopasowywania wzorca
$L\ =\ \{xcy\ :\ x,y \in (a + b)^*,\ y \in \mbox{\em Subwords\/} (x) \}$
nie jest bezkontekstowy.
Czy dopelnienie tego j"ezyka jest bezkontekstowe~?
\item Pokaza"c, "re j"ezyk $L\ =\ \{xcy^R\ :\ x,y \in (a + b)^*,\ y \in 
\mbox{\em Subwords\/} (x) \}$ jest bezkontekstowy.
\item (*)
Pokaza"c, "re dope"lnienie j"ezyka z poprzedniego zadania nie
jest j"ezykiem bezkontekstowym.

\item Rozstrzygnać, czy nast"epuj"acy j"ezyk jest bezkontekstowy:
$$L\ =\ \{u\$w^R\ :\ u,w \in \{a,b\}^+,\ w \textrm{ jest prefiksem i sufiksem } u \ \}$$
To samo pytanie dla dopełnienia tego jezyka.
\item
Udowodni"c, "re j"ezyk $L\ =\ 
\{a^ib^jc^k\ :i \ne j,\ i \ne k,\ j \ne k\ \}$
nie jest bezkontekstowy. 

Czy jego dope"lnienie 
jest bezkontekstowe~?
%%%%j"ezyka z poprzedniego zadania 
%%%%%%j"ezykiem bezkontekstowym ?
\item Czy j"ezyk $L\ =\ 
\{a^ib^ja^ib^j\ :i,j \ge 1\ \}$ jest bezkontekstowy ?

Czy jego dope"lnienie jest j"ezykiem bezkontekstowym ?

\item 
Udowodni"c, "re j"ezyk $L\ =\ \{ w w^R w : w \in (a+b)^* \}$ 
nie jest bezkontekstowy. 

Czy jego dope"lnienie 
jest bezkontekstowe~?
\item
Poka"r, "re j"ezyk  $\{x\#y^R\ :\ x,y \in \{0,1\}^+,\ [x]_2+1=[y]_2\}$ jest
bezkontekstowy.
\item 
Poka"r, "re j"ezyk  $\{x\#y\ :\ x,y \in \{0,1\}^+,\ [x]_2+1=[y]_2\}$ nie jest
bezkontekstowy.


\item Kt"ore z nast"epuj"acych j"ezyk"ow s"a bezkontekstowe~?
 \begin{enumerate}
 \item $\{ a^m b^n : m < n < 2m \} $
 \item $(a + b)^* - \{ (a^n b^n )^n : n \geq 1 \}$
 \item $ \{  w w^R w : w \in (a + b)^*  \} $
 \item $ \{ a^x b a^y b a^z : x+y = z \}$ 
  \item $ \{ a^x b a^y b a^z : x \cdot y = z \}$ 
 \end{enumerate}

\item Dowied"z, "re nast"epuj"ace j"ezyki nie s"a bezkontekstowe:
 \begin{enumerate}
 \item $\{ a^i b^j a^k : j = \mbox{ max } \{ i,k \} \} $
 \item $ \{ a^i b^i c^k : k \neq i \} $.
 \end{enumerate}

\item Czy j"ezyk
\[ \{ \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?

\item Niech $[n]_2$ oznacza  zapis binarny liczby naturalnej $n\ge 1$, 
pierwsz"a cyfr"a jest jedynka
(najbardziej znacz"aca). Czy nast"epuj"acy j"ezyk jest bezkontekstowy: \vskip 0.1cm
\centerline{$\ L_4\ =\ \{\ [n]_2\;[2n]_2\ :\ n\ge 1\ \}$}

\item 
 \begin{enumerate}
 \item
Udowodnij, "re zbi"or tautologii nad ustalonym sko"nczonym 
zbiorem zmiennych jest  bezkontekstowy (stanowi to uog"olnienie
zadania~(\ref{formuly_raz}) z sekcji~\ref{sect:gramatyki}).
\item Formu"ly nad przeliczalnym zbiorem zmiennych mo"rna przedstawi"c
jako j"ezyk nad sko"nczonym alfabetem, przyjmuj"ac 
indeksowanie zmiennych. Dok"ladniej, przyjmijmy, "re zbi"or
wszystkich formu"l jest generowany przez gramatyk"e
\begin{eqnarray*}
F & \to & \mbox{\bf true}  \,|\, \mbox{\bf false}  \,|\,
V  \,|\, ( F \vee F) \,|\, ( F\wedge F) \,|\, (\neg F) \\
V & \to & x I \\
I & \to & 0 \,|\, 1 J \\
J  & \to & J0 \,|\, J1 \,|\, \epsilon
\end{eqnarray*}
Np.~$ ( ( x101 \vee (\neg x0) ) \wedge (\neg ( \mbox{\bf false}
\vee  x101 )))  $ jest formu"l"a.

Udowodnij, "re zbi"or wszystkich tautologii nie jest 
bezkontekstowy\footnote{Stwierdzenie to wynika "latwo
z hipotezy P $\neq $ NP, ale nale"ry je dowie"s"c bez tej
hipotezy.}.

 \end{enumerate}

\item Niech $PAL$ onacza zbi"or palindrom"ow. Czy zachodzi implikacja: \vskip 0.3cm
 \centerline{L  bezkontekstowy \ \ $\Longrightarrow$\ \  $L \cap PAL$  bezkontekstowy\ ?}

\item
Sformuluj $uvwxy$-lemat o 
pompowaniu dla j"ezyk"ow liniowych w kt"orym $|uvxy| = O(1)$.

Dowied"z, "re j"ezyk $\{ a^i b^i c^j d^j : i, j \in \Nat \}$
nie jest liniowy.

\item
Dowied"z, "re
$L\ =\ \{x \in (a + b)^*, \#_a(x)=\#_b(x) \}$ nie
jest liniowym j"ezykiem bezkontekstowym.

\item
Udowodnij, "re zbi"or s"l"ow $w$ nad alfabetem $\{a,b\}$ maj"acych
t"e sam"a liczb"e liter $a$ co $b$ nie jest liniowym j"ezykiem 
bezkontekstowym.



\item \noindent Kt"ory z nast"epuj"acych j"ezyk"ow jest bezkontekstowy.  W przypadku gdy
j"ezyk jest bezkontekstowy wypisa"c gramatyk"e bezkontekstow"a. W zadaniu $[x]_2$ oznacza 
binarny zapis liczby
$x$, oraz $w^R$ oznacza odwr"ocenie s"lowa $w$. \vskip 0.3cm
 \begin{enumerate}
 \item 
%%%% {\bf (A)}\ \ \ 
{$L_1\ =\  \{[x]_2\ \&\ [y]_2\ :\ 1 \le x \le y\ \}$.}
%%%% \ \ \ \ \ {\bf (B)}\ \ \ 
 \item {$L_2\ =\  \{[x]_2\ \&\ [y]_2^R\ :\ 1 \le x \le y\ \}$.}
 \end{enumerate}

\item Niech $\mathbf{D_1, D_2}$ oznacza zbi"or poprawnych ci"ag"ow nawiasowych  jednego typu
({\em okr"ag"le })
 i dw"och typ"ow nawias"ow ({\em okr"ag"le } i {\em kwadratowe}), odpowiednio, w"l"acznie ze s"lowem pustym.
Czy następujące języki są bezkontekstowe
 \begin{enumerate}
 \item $\{\ u\#v^R\ :\ uv \in \mathbf{D_1}\ \}$,
 \item $\{\ u\#v^R\ :\ uv \in \mathbf{D_2}\ \}$~?
 \end{enumerate}
\item Niech $L$ b"edzie zbiorem s"l"ow w alfabecie trzyelementowym, kt"ore 
nie zawieraj"a s"lowa postaci $xx$, dla $x\ne \epsilon$. Udowodni"c, "re $L$ 
nie jest bezkontekstowy.

\item Poda"c przyk"lad j"ezyka bezkontekstowego nad alfabetem trzyelemnentowym, kt"orego dope"lnienie
jest niesko"nczone i nie zawiera s"l"ow postaci $xx$, dla $x\ne \epsilon $.

\end{enumerate}




\subsection{Automaty ze stosem}
\begin{enumerate}


\item
Skonstruowa"c automaty ze stosem rozpoznaj"ace poznane wcze"sniej j"ezyki
bezkontekstowe: zbi"or palindrom"ow, zbi"or poprawnie uformowanych ci"ag"ow
nawias"ow, zbi"or s"l"ow, kt"ore maj"a dwa razy wi"ecej $b$ ni"r $a$, 
zbi"or ci"ag"ow,
kt"ore nie s"a postaci $ww$.

\item Dla liczby naturalnej $n$, niech $\mbox{bin}(n) \in \{ 0,1\}^* $
b"edzie binarnym przedstawieniem liczby $n$. 
Skonstruowa"c automat ze stosem rozpoznaj"acy j"ezyk
\[ \{ \mbox{bin}(n)\, \$ \, \mbox{bin}(n+1)^R \, :\, n \in N \} \]

\item 
Skonstruowa"c automat ze stosem rozpoznaj"acy j"ezyk
\[ \{ \mbox{bin}(n)\, \$ \, \mbox{bin}(3*n)^R \, :\, n \in N \} \]
Uog"olni"c tez"e zadania\footnote{Mo"rna zacz"a"c
od przyk"ladu 
$\{ \mbox{dec}(n) \, \$ \, \mbox{dec}(2006*n)^R \, :\, n \in N \}
$,
gdzie  $\mbox{dec}(n) \in \{ 0,1,\ldots , 9\}^* $ jest 
 dziesi"etnym przedstawieniem liczby $n$.}.

\item Dowie"s"c, "re dla ka"rdego automatu ze stosem $A$, mo"rna
skonstruowa"c automat ze stosem {\em o dw"och stanach} $A'$, taki "re
$L(A) = L(A')$.

\item Dowie"s"c, "re automatowi $A'$ z poprzedniego zadania mo"rna
postawi"c dalszy wym"og, "re ka"rde przej"scie jest postaci
\[ q, a, Z\, \rightarrow_{A'} \, q' , \alpha \]
gdzie $|\alpha | \leq 2$ ($q,q'$ dowolne).



\item Dowie"s"c, "re dla ka"rdego automatu ze stosem $A$, mo"rna
skonstruowa"c r"ownowa"rny mu automat ze stosem $A''$, w kt"orym
ka"rde przej"scie jest postaci {\em push\/} lub {\em pop\/}, tzn.
\[ q, a, Z\, \rightarrow_{A''} \, q' , YZ \]
lub
\[ q, a, Z\, \rightarrow_{A''} \, q' , \epsilon \]
 Czy dla takich automat"ow 
mo"rna nadal ograniczy"c liczb"e stan"ow?
\item Maj"ac dany automat ze stosem  akceptuj"acy j"ezyk $L$,
skonstruowa"c automaty ze stosem akceptuj"ace nast"epuj"ace j"ezyki:
\begin{itemize}
\item $\mbox{Prefix}(L) = \{ w\, : \, (\exists v) wv \in L \}$
\item $\mbox{Suffix}(L) = \{ w\, : \, (\exists u) uw \in L \}$
\item $\mbox{Subword}(L) = \{ w\, : \, (\exists u,v) uwv \in L \}$
\item  $L^R = \{ w^R \, : \,  w \in L \}$
\item (*)  $\mbox{Cycle}(L) = \{ vw\, : \,  wv \in L \}$
\end{itemize}
\item  Maj"ac dany automat ze stosem  akceptuj"acy j"ezyk $L$
i automat sko"nczony  akceptuj"acy j"ezyk $R$,
skonstruowa"c automaty ze stosem akceptuj"ace nast"epuj"ace j"ezyki:
\begin{itemize}
\item $L R^{-1}$
\item $R^{-1} L$
\item $L \cap R$
\end{itemize}

\item Niech $\#_s(w)$ oznacza liczb"e symboli $s$ w s"lowie $w$, oraz $PREF(u)$ oznacza zbi"or prefiks"ow s"lowa $u$.
Ponadto oznaczmy przez $max(w),\ min(w),\ med(w)$ opowiednio maksimum, minimum i median"e liczb
$\#_a(w),\#_b(w),\#_c(w)$.
% $max(w)=\max\ \{\#_a(w),\#_b(w),\#_c(w)\}$, $min(w)=\min\
%\{\#_a(w),\#_b(w),\#_c(w)\}$,\vskip 0.3cm
 %$med(w)=median\ \{\#_a(w),\#_b(w),\#_c(w)\}$
 \vskip 0.3cm
 \noindent Kt"ory z nast"epuj"acych j"ezyk"ow jest regularny, a kt"ory bezkontekstowy? 
%%%\vskip 0.3cm {\bf (A)}\ \ \ 
 \begin{enumerate}
 \item
{$L_1\ =\  
\{u\in (a\cup b\cup c)^*\ :\ \forall\ w\in PREF(u)\ max(w)-min(w) \le 13\ \}$.}
 \item
%%%\{\bf (B)}\ \ \ 
{ $L_2\ =\ \{u\in (a\cup b\cup c)^*\ :\ \forall\ w\in PREF(u)\ max(w)-med(w) \le 13\ \}$.}
 \end{enumerate}



\item Dla danych j"ezykow regularnych $L$ i $M$, skonstruowa"c 
automat ze stosem
rozpoznaj"acy j"ezyk $\bigcup_{i\in N} (L^i \cap  M^i )$.
Uwaga: ten zbi"or nie
musi by"c regularny.
\item Dowie"s"c, "re dla ka"rdego automatu ze stosem $A$ istnieje
sta"la $C$ (zale"rna od automatu), taka, "re dla ka"rdego s"lowa
$w \in Z(A)$, istnieje obliczenie akceptuj"ace (przez pusty stos)
o d"lugo"sci $\leq C |w|$. Wskaz"owka: oszacowa"c wysoko"s"c stosu
w obliczeniu akceptuj"acym.
\item  Niech $A$ b"edzie automatem ze stosem. Dowie"s"c, "re zbi"or 
s"l"ow, kt"ore s"a mo"rliwymi zawarto"sciami stosu automatu $A$, jest
j"ezykiem regularnym.
Formalnie, mamy na my"sli zbi"or
\[ \{ \alpha \in \Gamma^* \, :\, (\exists w, v\in \Sigma^*) (\exists q\in Q)\,
q_I ,w ,Z_I\, \vdash_{A} \, q, v, \alpha \} \]
Wywnioskowa"c st"ad, "re zbi"or 
s"l"ow, kt"ore s"a mo"rliwymi zawarto"sciami stosu automatu $A$ w jakim"s
obliczeniu {\em akceptuj"acym}, jest
j"ezykiem bezkontekstowym.
\item Automat ze stosem $ A = (\Sigma , \Gamma ,Q,q_I ,Z_I , \delta ,F)$
nazywamy {\em deterministycznym}, je"sli w ka"rdej sytuacji mo"rliwy
jest co najwy"rej jeden ruch. Dok"ladniej:
\begin{itemize}
\item je"sli, dla pewnej pary $q,Z$,  zachodzi
$q,\epsilon ,Z \rightarrow_A p,\alpha $ przy pewnych $p, \alpha $, to
dla "radnego $\sigma \in \Sigma $, nie zachodzi 
$q, \sigma ,Z \rightarrow_A p',\alpha' $, dla "radnych
$p', \alpha'$;
\item dla ka"rdych $q, \sigma ,Z$, istnieje co najwy"rej jedna para
$p, \alpha $, taka "re $q, \sigma ,Z \rightarrow_A p, \alpha $.
\end{itemize}
J"ezyk bezkontekstowy  jest {\em deterministyczny\/} je"sli 
jest rozpoznawany przez pewien deterministyczny automat ze stosem
(w sensie stan"ow akceptuj"acych, tzn.~$L = L(A)$).

Dowie"s"c, "re j"ezyk 
$\{ a^n b^n : n \in \Nat \}$ $\cup $
$\{ a^n b^{2n} : n \in \Nat \}$
 nie jest
{ deterministycznym\/}  j"ezykiem bezkontekstowym.

{\em Wskaz"owka.\/}\footnote{Rozwiązanie podane przez studenta, pana Adama Wilczyńskiego.}
Zakładając, że istnieje deterministyczny automat $A$ 
rozpoznający ten język, rozważyć automat $A'$, 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 \Nat \} $.


\item 
Wykaza"c, "re zbi"or palindrom"ow nad alfabetem dwuelementowym nie jest
{ deterministycznym\/}  j"ezykiem bezkontekstowym.
%%\item 

{\em Wskaz"owka.\/} Zastosować metodę z poprzedniego zadania. Przy pomocy
hipotetycznego automatu deterministycznego rozpoznającego palindromy można
np.\ skonstruować automat rozpoznający język
$\{ c a^n b a^n c  a^n b a^n c: n \in \Nat \} $.

%{\em Uwaga.} 
%Dope"lnienie j"ezyka z poprzedniego zadania jest j"ezykiem
%bezkontekstowym, patrz zadanie~\ref{palindromy i nie}
%z punktu~\ref{sect:gramatyki}.


%\item
%Udowodni"c, "re zbi"or wszsytkich mo"rliwych zawarto"sci stosu (traktowanych
%jako s"lowa) kt"ore mog"a wyst"api"c w obliczeniach danego automatau stosowego
%jest j"ezykiem regularnym.

%******* nowy tekst


%\item Podaj przyk"lad j"ezyka bezkontekstowego takiego. "re 
%$\sqrt{L}$ nie jest bezkontekstowy.

%%%%\item Czy zbi"or mo"rliwych zawarto"sci stosu automatu
%%%%stosowego (dla wszsytkich mo"rliwych wej"s"c) jest regularny ?
%\item Udowodnij, "re ka"rdy j"ezyk bezkontekstowy nad alfabetem
%%%%jednoelementowym jest regularny.



\end{enumerate}




%%%%%%
%%%%%%



\subsection{W"lasno"sci j"ezyk"ow bezkontekstowych}
\begin{enumerate}


\item
Podaj przyk"lad j"ezyka bezkontekstowego $L$ t."re 
j"ezyk 
%%$L\ =\ \{x\ :\ xy \in L,\ |x|=|y|,$ dla pewenego $y \}$ 
$L\ =\ \{x\ :\ (\exists y) \,  |x|=|y| \, \wedge \, xy \in L \} $
nie 
jest bezkontekstowy.




\item
Udowodni"c, "re przeci"ecie j"ezyka (deterministycznego) bezkontekstowego 
z regularnym jest te"r j"ezykiem  (deterministycznym) bezkontekstowym.
\item
Przeplotem s"l"ow $w$ i $v$ nazwiemy dowolne s"lowo d"lugo"sci
$|w| + |v|$, kt"ore mo"rna rozbi"c na roz"l"aczne podci"agi $w$ i $v$.
%Na przyk"lad, przeplotami s"l"ow $ab$ i $acb$ s"a s"lowa
%$abacb$, $aabcb$, $acabb$, $acbab$, $aacbb$. Przeplotem j"ezyk"ow
$L$ i $M$ jest zbi"or wszystkich mo"rliwych przeplot"ow
s"l"ow $w \in L$, $v \in M$. J"ezyk ten oznaczamy $L \parallel M$.
Udowodnij, ze przeplot j"ezyka bezkontekstowego i regularnego jest
j"ezykiem bezkontekstowym.
Podaj przyk"lad j"ezyk"ow bezkontekstowych $L$ i $M$, dla
kt"orych $L \parallel M$ nie jest j"ezykiem bezkontekstowym.

\item
Domkni"ecie przeplotne j"ezyka $L$ okre"slamy przez
$L^{\sharp } = L \, \cup \, (L \parallel L) \, \cup
\, (L \parallel L  \parallel L) \, \cup \ldots $. 
%Poda"c przyk"lad 
%j"ezyka regularnego $L$ nad dwuelementowym alfabetem, dla kt"orego
%$L^{\sharp }$ nie jest j"ezykiem regularnym.
Wykaza"c, "re operacja domkni"ecia przeplotnego j"ezyka sko"nczonego
mo"re da"c w wyniku j"ezyk kt"ory nie jest bezkontekstowy.

\item
Udowodni"c, "re je"sli $X$, $Y$ s"a j"ezykami regularnymi to
j"ezyk\vskip 0.3cm 
\centerline{ $L\ =\ \sum_{n \ge 1} X^n \cap Y^n$}
\vskip 0.1cm \noindent
jest bezkontekstowy.
\item
Poda"c przyk"lad j"ezyk"ow regularnych $X,\ Y$ t."re 
\vskip 0.3cm 
\centerline{ $\sum_{n \ge 1} (X^n \cap Y^n)\ =\ \{a^nb^n\ :\ n \ge 1\}$}
\item
Podaj j"ezyki regularne $X,\ Y, Z$ t."re j"ezyk
\vskip 0.3cm 
\centerline{ $\sum_{n \ge 1} (X^n \cap Y^n \cap Z^n)$}
nie jest bezkontekstowy.

\item
Wska"r  j"ezyk bezkontekstowy $L$, dla kt"orego
$\sqrt{L} = \{ w : ww \in L \} $ nie jest j"ezykiem
bezkontekstowym.

\item
Podaj przyk"lad j"ezyka bezkontekstowego takiego. "re
$\{x\ :\ x^k \in L$ dla pewnego $k \}$ nie jest bezkontekstowy.

\item
Rozwa"rmy nast"epuj"acy morfizm:\\
\centerline{$h(a)=a,\ h(b)=b,\ h(a')=a,\ h(b')=b$}
oraz $h(x) = \epsilon$ dla symboli $x \in \{a,b,a',b'\}$ dla kt"orych morfizm
nie zosta"l zdefiniowany powy"rej.
Wykaza"c, "re j"ezyk $EQ(h,g) = \{ w : h(w) = g(w) \}$ 
nie jest bezkontekstowy.

\item
Udowodnij, "re je"sli $U$ jest regularny to nast"epuj"acy j"ezyk jest 
bezkontekstowy\\
\centerline{$\{xy^R\ :\ x \ne y,\ xy \in U\}$}

\item
J"ezyk ma w"lasno"s"c prefiksow"a, gdy dla ka"rdych 
%%dwu 
dw"och
s"low z tego
j"ezyka jedno z nich jest prefiksem drugiego.
Wyka"r, "re je"sli j"ezyk bezkontekstowy ma w"lasno"s"c prefiksow"a
to jest on regularny.




\item
Niech $L \subseteq \{a,b\}^*$ b"edzie j"ezykiem regularnym oraz
$h, g$ b"ed"a morfizmami.
Udowodni"c, "re nast"epuj"acy j"ezyk jest liniowym j"ezykiem
bezkontekstowym
\\
\centerline{$ \{ h(u)c(g(u))^R\ :\ u \in L\}$}
\item
Udowodnij, "re przeci"ecie  liniowego j"ezyka bezkontekstowego 
z regularnym jest
j"ezykiem liniowym.

% (skorzystaj ze wzmocnionego lematu o pompowaniu
%w kt"orym $|uvxy|$ jest ograniczone przez sta"l"a).
\item \label{Min}
Dla j"ezyka $L$ okre"slamy $\mbox{Min} (L)$ jako zbi"or 
s"l"ow w $L$ minimalnych ze wzgl"edu na porz"adek bycia prefiksem.
(Zatem $u \in \mbox{Min} (L)$ $\Leftrightarrow $ nie istniej"a
$v \in L$ oraz $w \neq \epsilon $ takie, "re $v w \in L$.)
Udowodnij, "re dla deterministycznego j"ezyka bezkontekstowego $L$
j"ezyk $\mbox{Min} (L)$ jest  r"ownie"r deterministycznym j"ezykiem
bezkontekstowym.
\item
Niech $L\ =\ \{a^ib^jc^k\ :\ k \ge i \ lub\ k \ge j\}$. Poka"r, "re 
$Min(L)$ nie jest j"ezykiem bezkontekstowym.
\item Zbi"or $\mbox{Max} (L)$
okre"slamy analogicznie jak zbi"or $\mbox{Min} (L)$
w zadaniu~\ref{Min}.
Podaj przyk"lad j"ezyka bezkontekstowego 
$L$, dla kt"orego $\mbox{Max} (L)$ nie jest
j"ezykiem  bezkontekstowym.



\item
Niech 
$h_1, h_2$ b"ed"a morfizmami takimi, "re alfabet wyj"sciowy nie zawiera \$.
Wyka"r, "re j"ezyki $\{ x\$y^R\ :\ h_1(x)=h_2(x)\}$ i 
$\{ x\$y^R\ :\ h_1(x) \ne h_2(x)\}$ s"a liniowymi j"ezykami bezkontekstowymi.


\item
Podzbi"or $M \subseteq \Nat^k$ nazywamy {\em liniowym\/} je"sli mo"rna
go przedstawi"c $M = \{ \vec{a} + n \cdot \vec{b} : n \in \Nat \}$,
dla pewnych wektor"ow $\vec{a}, \vec{b} \in \Nat^k$, a 
{\em semi-liniowym\/}, je"sli jest sum"a sko"nczenie wielu zbior"ow
semi-lniowych.
 \begin{enumerate}
 \item Udowodnij, "re zbi"or d"lugo"sci s"l"ow j"ezyka bezkontekstowego
 jest semi-liniowy.
 \item (*)
 Udowodnij
 {\em twierdzenie Parikha\/}
 g"losz"ace, "re dla j"ezyka  bezkontekstowego $L \subseteq \Sigma^*$
 zbi"or ($\subseteq \Nat^{ |\Sigma |}$)
 wektor"ow liczby wyst"apie"n liter z $\Sigma $ 
 w s"lowach z $L$
%%j"ezyka bezkontekstowego 
 jest semiliniowy.
 \end{enumerate}
 
%\item
%Niech $X \subseteq \{a,b\}^*$ Poka"r "re j"ezyk $X\$X$ jest regularny wtedy
%i tylko wtedy gdy $X$ jest regularny.

\item Przypomnijmy pojęcie odległości Hamminga, określonej dla słów
tej samej długości (zadanie~\ref{properties_reg}.\ref{Hamming}) 
\[ 
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~?

\item Czy nast"epuj"ace stwierdzenia s"a prawdziwe: 
\begin{enumerate}
\item
Istnieje niesko"nczony zbi"or s"l"ow $L$ nad sko"nczonym alfabetem taki,
"re ani $L$ ani dope"lnienie $L$ nie zawieraj"a niesko"nczonego j"ezyka regularnego.
\item   To samo, ale
wymagamy dodatkowo, aby $L$ by"l bezkontekstowy.
\end{enumerate}
\end{enumerate}

\section{Teoria oblicze"n}
\subsection{Maszyny Turinga} \label{sect:Turing}
\begin{enumerate}


\item Skonstruowa"c maszyn"e Turinga obliczaj"ac"a funkcj"e $2^n $
reprezentowan"a {\em unarnie}. Bardziej dok"ladnie,
zak"ladamy, "re alfabet wej"sciowy sk"lada si"e z jednego symbolu,
powiedzmy $\{ 1 \}$.  Je"sli na wej"sciu dany jest ci"ag
$n$ jedynek, (tzn.\ konfiguracja wej"sciowa jest $q_0 1^n $), to
po wykonaniu obliczenia konfiguracja powinna by"c $q_f 1^{2^n }$.
\item Skonstruowa"c maszyn"e Turinga obliczaj"ac"a funkcj"e 
$\lceil \log n \rceil $
reprezentowan"a {\em unarnie}.
\item Przyjmijmy $\Sigma = \{ 0,1 \}$. 
Skonstruowa"c maszyny Turinga rozpoznaj"ace nast"epuj"ace j"ezyki:
\begin{enumerate}
\item zbi"or palindrom"ow
\item $\{ w\$ w \, :\, w \in \Sigma^* \}$
\item  $\{ w w \, :\, w \in \Sigma^* \}$
\item zbi"or ci"ag"ow reprezentuj"acych binarnie liczby pierwsze.
\end{enumerate}
\item Graf zorientowany o $n$ wierzcho"lkach ponumerowanych 
$0,1,\ldots ,n-1$, reprezentujemy ci"agiem zer i jedynek d"lugo"sci $n^2 $,
takim, "re $k$-ty bit jest 1 o ile istnieje kraw"ed\'{z} z
wierzcho"lka o numerze $i$ do wierzcho"lka o numerze $j$, gdzie
$k = i \cdot n + j + 1$.
\begin{enumerate}
\item Skonstruowa"c {\em niedeterministyczn"a} maszyn"e Turinga
rozpoznaj"ac"a zbi"or s"l"ow zero-jedynkowych, kt"ore w powy"rszy
spos"ob reprezentuj"a te grafy, w kt"orych istnieje "scie"rka z
wierzcho"lka o numerze $0$ do wierzcho"lka o numerze $n-1$.
\item  Skonstruowa"c maszyn"e {\em deterministyczn"a} realizuj"ac"a
to samo zadanie.
\end{enumerate}
\item Przypomnijmy, "re dwie maszyny Turinga o tym samym alfabecie
wej"sciowym uwa"ramy za {\em r"ownowa"rne} o ile akceptuj"a ten sam
j"ezyk. Udowodni"c, "re dla ka"rdej maszyny Turinga istnieje 
r"ownowa"rna jej maszyna posiadaj"aca dok"ladnie jeden stan akceptuj"acy
i taka, "re w konfiguracji akceptuj"acej g"lowica znajduje si"e nad
pierwsz"a kom"ork"a ta"smy (tzn.\ konfiguracja akceptuj"aca jest
postaci $q_f \mbox{ co"s}$).
\item Dla danej {\em niedeterministycznej} maszyny Turinga skonstruowa"c
r"ownowa"rn"a maszyn"e {\em deterministyczn"a}.
\item Dla danych deterministycznych 
maszyn Turinga $M_1 $ i $M_2$ skonstruowa"c
deterministyczne   maszyny rozpoznaj"ace j"ezyki
\begin{itemize}
\item $L(M_1 ) \cup L(M_2 )$
\item $L(M_1 ) \cap L(M_2 )$
\item $L(M_1 )  L(M_2 )$
\item $L(M_1 )^{*}$.
\end{itemize}
\item Udowodni"c, "re dla ka"rdej maszyny Turinga nad alfabetem 
wej"sciowym $\{ 0,1\}$, istnieje 
r"ownowa"rna jej maszyna, kt"orej alfabet {\em wszystkich} symboli roboczych
obejmuje jedynie symbole 0,1,$B$.

\item Powiemy, "re maszyna Turinga jest {\em write-once} je"sli
mo"re pisa"c tylko w pustych kom"orkach ta"smy, a symbol raz napisany
nie mo"re by"c zast"apiony "radnym innym symbolem (w szczeg"olno"sci
nie mo"re by"c ``zmazany'' tj.\ zast"apiony przez ``blank''). 
%M"owi"ac
%bardziej formalnie, dopuszczalne s"a jedynie przej"scia postaci
Dla dowolnej maszyny Turinga z jedn"a ta"sm"a, skonstruowa"c
maszyn"e {\em write-once} z 
%%%%nie wi"ecej ni"r trzema 
dwiema ta"smami, kt"ora
akceptuje ten sam j"ezyk. 
%(Wolno powi"ekszy"c r"ownie"r alfabet roboczy.)

(*) Dowie"s"c, "re maszyny typu {\em write-once} z
{\em jedn"a\/} ta"sm"a akceptuj"a jedynie j"ezyki regularne.
\item  Dla dowolnej  maszyny Turinga 
%%%%$M$
(nad dowolnym alfabetem), skonstruowa"c r"ownowa"rn"a 
maszyne o {\em jednej ta"smie\/} i  {\em czterech\/} stanach.
 (Wolno powi"ekszy"c  alfabet
roboczy.)
\item Poj"ecie automatu ze stosem mo"rna rozszerzy"c do automatu
z $k$ stosami, $k \geq 2$. Dowie"s"c, "re dla ka"rdej maszyny Turinga
istnieje r"ownowa"rny jej deterministyczny automat z dwoma stosami.
Wywnioskowa"c st"ad, "re automat z $k$ stosami, $k > 2$ mo"re
by"c symulowany przez automat z 2 stosami (symulacj"e t"e mo"rna
r"ownie"r opisa"c bezpo"srednio).
\item Udowodni"c, "re je"sli automat sko"nczony wyposa"ry"c dodatkowo
w kolejk"e, to otrzymany model ma si"le obliczeniow"a maszyny Turinga,
tzn.~dla dowolnej maszyny istnieje automat z kolejk"a, kt"ory rozpoznaje
ten sam j"ezyk.
\item  \label{liczniki}
Automat z $k$ licznikami $c_1, \ldots ,c_k$,
okre"slamy podobnie jak automat z $k$ stosami, z tym, "re liczniki
zawieraj"a liczby naturalne, a dost"epne operacje na
licznikach s"a 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"scia takiego
automatu s"a 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"smy, lecz zak"ladamy, 
"re w chwili pocz"atkowej dana wej"sciowa jest warto"sci"a
licznika $c_1$, a pozosta"le liczniki maj"a
warto"s"c 0.
 Dowie"s"c najpierw, "re dla ka"rdej maszyny Turinga
nad alfabetem $\{ 1\}$ istnieje r"ownowa"rny jej automat z 4
licznikami. Nast"epnie wykaza"c, "re liczba licznik"ow mo"re by"c
dalej zredukowana do trzech. (Ograniczenie alfabetu maszyny
Turinga nie jest istotne, bo s"lowa nad alfabetem $n$--literowym
mo"rna r"ownie"r "latwo ``przerobi"c'' na liczby naturalne w
systemie unarnym.)
\end{enumerate}

\subsection{Obliczalno"s"c i nierozstrzygalno"s"c} \label{sect:obli}
\begin{enumerate}


\item Udowodni"c r"ownowa"rno"s"c nast"epuj"acych warunk"ow
  \begin{itemize}
  \item j"ezyk $L$ jest cz"e"sciowo obliczalny,
  \item j"ezyk $L$ jest dziedzin"a pewnej funkcji cz"e"sciowo
  obliczalnej,
    \item j"ezyk $L$ jest zbiorem warto"sci pewnej funkcji cz"e"sciowo
  obliczalnej,
    \item j"ezyk $L$ jest  zbiorem warto"sci  pewnej funkcji 
  obliczalnej.
  \end{itemize}
\item Udowodni"c, "re    j"ezyk $L$ jest  obliczalny, wtedy i tylko
wtedy, gdy jest sko"nczony lub jest zbiorem warto"sci  pewnej funkcji 
  obliczalnej rosn"acej.
\item Udowodni"c nast"epuj"ace twierdzenie Turinga--Posta~:
je"sli zar"owno j"ezyk jak i jego uzupe"lnienie s"a cz"e"sciowo
obliczalne, to s"a r"ownie"r obliczalne.
\item Udowodni"c, "re istnieje zbi"or cz"e"sciowo obliczalny,
kt"orego uzupe"lnienie nie zawiera "radnego niesko"nczonego
zbioru cz"e"sciowo obliczalnego.

\item Udowodni"c, "re istnieje  automat
z dwoma ({\em sic~!}) licznikami $A$ taki, "re
nie jest rozstrzygalne, czy $A$ zatrzymuje si"e dla danej
wej"sciowej $n$. Wskaz"owka~: wykorzysta"c zadanie~\ref{liczniki}.
\item Udowodni"c nierozstrzygalno"s"c nast"epuj"acego
{\em problemu  Posta}.

Dane s"a dwie listy s"l"ow~: 
$u_1 ,\ldots ,u_n \in \Sigma^*$ i $w_1 ,\ldots ,w_n \in \Sigma^*$.
Pytanie, 
czy istnieje ci"ag indeks"ow $i_1 ,\ldots ,i_m \in \{ 1,\ldots ,n\}$,
taki, "re 
$u_{i_1} \ldots u_{i_n} = w_{i_1} \ldots w_{i_n} $ ?
Je"sli taki ci"ag istnieje, to s"lowo 
$u_{i_1} \ldots u_{i_n}$ ($ = w_{i_1} \ldots w_{i_n} $) nazywamy
{\em rozwi"azaniem\/} danej instancji problemu Posta.

Wskaz"owka~: Rozwa"ry"c zmodyfikowany problem Posta, w kt"orym dodatkowo
wymaga si"e, by pierwszymi s"lowami w rozwi"azaniu by"ly $u_1$ i
$w_1$ (tzn.~$i_1 = 1$). Redukcja zmodyfikowanego problemu do oryginalnego
problemu Posta nie jest trudna. 
Z kolei przedstawi"c algoerytm, kt"ory dla dowolnej maszyny Turinga
$M$ i jej wej"scia $w$ konstruuje instancj"e $P$ zmodyfikowanego
problemu Posta w ten spos"ob, "re $P$ ma rozwi"azanie wtedy i tylko
wtedy, gdy $M$ akceptuje $w$. Rozwi"azaniem $P$ (o ile istnieje)
b"edzie w"la"snie akceptuj"ace obliczenie $M$ na $w$.

\item Dowie"s"c, "re nast"epuj"ace problemy s"a nierozstrzygalne~:
\begin{itemize}

\item Dana gramatyka bezkontekstowa $G$ nad alfabetem
$\Sigma$. Pytanie~: czy $L(G) = \Sigma^*$~? (Tzw.~problem 
{\em uniwersalno"sci\/}.)
Wskaz"owka~: 
Dla  maszyny Turinga $M$, {\em udane obliczenie\/}
jest ci"agiem $c_0 \# c_1 \# \ldots \# c_f $,
gdzie $c_i$ s"a konfiguracjami $M$,
$c_0$ jest konfiguracj"a pocz"atkow"a, $c_f$ akceptuj"ac"a,
oraz $c_i \vdash_M c_{i+1}$. Nale"ry przedstawi"c algorytm, 
kt"ory dla dowolnej maszyny
$M$ konstruuje gramatyk"e $G_M$ generuj"ac"a wszystkie
ci"agi, kt"ore nie s"a udanymi obliczeniami. A zatem, gdyby"smy potrafili
rozstrzyga"c problem uniwersalno"sci, mogliby"smy 
r"ownie"r rozstrzyga"c problem niepusto"sci ($L(M) \neq \emptyset$~?)
dla maszyn Turinga, co jest niemo"rliwe (na mocy twierdzenia Rice'a).

\item Dane dwie gramatyki bezkontekstowe $G_1, G_2$. Pytanie~:
czy $L (G_1) \cap L (G_2) \neq \emptyset $~?
Wskaz"owka~: Podobnie jak poprzednie zadanie, ale nale"ry wykorzysta"c
operacj"e lustrzanego odbicia.
\item Dana gramatyka bezkontekstowa $G$.
 Pytanie~: czy $G$ jest jednoznaczna (tzn.~dla ka"redego
s"lowa w $L(G)$ istnieje dok"ladnie jedno drzewo wyprowadzenia).

Wskaz"owka~: wykorzysta"c problem Posta.

\end{itemize}

\item
Czy nast"epu"acy problem $X$ jest rozstrzygalny: \\
  \hspace{1cm}Dana gramatyka
    bezkontekstowa $G$, sprawdzi"c czy $L(G) $ zawiera palindrom.

\item
Za"l"o"rmy, "re wiemy "re jednotasmowa deterministyczna maszyna Turinga $M$ 
wykonuje zawsze co najwyzej jeden ''nawr"ot'' (to znaczy glowica przesuwa sie w prawo
a od pewnego momentu ju"r tylko w lewo). Czy problem ``$w \in L(M)$'' jest
rozstrzygalny, gdzie 
$w$ jest s"lowem wej"sciowym a $L(M)$ oznacza zbi"or s"l"ow akceptowanych przez $M$
stanem akceptuj"acym.

\item
Czy  nast"epuj"acy problem jest rozstrzygalny.\
  Dane s"a dwa   s"lowa $u,w \in \Sigma^*$ oraz liczba $k$,  sprawdzi"c czy 
%%%%\vskip0.1cm  \centerline{$
\[
\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"e wyst"apie"n s"lowa $w$ jako pods"lowo  
$x$ (wyst"apienia nie
musz"a by"c roz"l"aczne). 
\end{enumerate}

\subsection{Hierarchia Chomsky'ego}

\begin{enumerate}
\item Dowie"s"c, "re ka"rd"a gramatyk"e {\em monotoniczn"a}, czyli
o regu"lach  $\alpha \to \beta$, gdzie $ |\beta | \geq |\alpha | $,
mo"rna sprowadzi"c do postaci, w kt"orej ka"rda regu"la ma form"e
\[
\alpha X \beta \to \alpha \gamma \beta
\]
gdzie $X \in V$, $\alpha , \beta ,  \gamma \in (\Sigma \cup V)^*$,
$  \gamma \neq \varepsilon $ ($V$ -- zbi"or symboli nieterminalnych,
$\Sigma $ -- zbi"or symboli terminalnych).

{\em Uwaga.} Przy powy"rszym sprowadzeniu trzeba na og"o"l powi"ekszy"c
zbi"or symboli nieterminalnych.

\item Dowie"s"c, "re j"ezyki kontekstowe, to dok"ladnie j"ezyki rozpoznawane
przez niedeterministyczne {\em automaty liniowo ograniczone\/}.

{\em Uwaga.} Automaty liniowo ograniczone s"a okre"slone podobnie jak
maszyny Turinga, z tym, "re jedyn"a dost"epn"a pami"eci"a
s"a kom"orki ta"smy zaj"ete na pocz"atku przez s"lowo wej"sciowe
(przy czym koniec s"lowa jest zaznaczony specjalnym markerem).

\item Dowie"s"c, "re iloraz j"ezyka kontekstowego przez 
j"ezyk regularny mo"re nie by"c j"ezykiem obliczalnym.

{\em Wskaz"owka.} Wykorzysta"c j"ezyk oblicze"n maszyny Turinga,
kt"ora akceptuje j"ezyk nieobliczalny.

Wywnioskowa"c dalej, "re ani j"ezyki kontekstowe, ani j"ezyki obliczalne
nie s"a zamkni"ete na ilorazy przez j"ezyki  regularne.


\item Dowie"s"c, "re j"ezyki cz"e"sciowo  obliczalne {\bf s"a}
zamkni"ete na ilorazy przez j"ezyki cz"e"sciowo  obliczalne.

\item Kt"ore z czterech klas hierarchii Chomsky'ego s"a zamkni"ete
na operacje $\cup, \cap, - $~?

\end{enumerate}

\subsection{Z"lo"rono"s"c obliczeniowa}
\begin{enumerate}
\item {\em Konstruowalno"s"c pami"eciowa}.
Skonstruowa"c maszyn"e Turinga {\em off-line}, kt"ora dla
wej"scia $w$ o d"lugo"sci $n$ zu"rywa dok"ladnie $f(n)$
kom"orek pami"eci roboczej, gdzie 
\[  f(n) = 2n, n^2, n^k , 2^n, \log n, \ldots \]

\item {\em Konstruowalno"s"c czasowa}.
Skonstruowa"c maszyn"e Turinga,  kt"ora dla
wej"scia $w$ o d"lugo"sci $n$ wykonuje dok"ladnie $f(n)$
krok"ow, 
gdzie 
$f(n) = 2n, 3n, n^2, n^k , 2^n, 2^{2^n} , \ldots $.

\item Dowie"s"c, "re klasy $P$, {\em NP} i {\em PSPACE\/}
s"a zamkni"ete na operacj"e *.
\item \label{domino}
{\em Problem domina.} Instancja problemu domina obejmuje
liczb"e naturaln"a $M$ dan"a unarnie oraz sko"nczony zbi"or 
{\em wzorc"ow kostek domina\/}, tzn.~wektor"ow postaci
({\em up, down, left, right \/}), gdzie 
{\em up, down, left\/} i {\em right \/} s"a binarnie zadanymi
liczbami, kt"ore w tym kontek"scie nazywamy {\em kolorami\/}.
(Liczba kolor"ow nie jest ograniczona, a wi"ec zale"ry od danej
instancji problemu.) Pytanie brzmi: czy kwadrat $M \times M$
mo"rna 
%%u"lo"ry"c 
pokry"c
kostkami domina w ten spos"ob, "re s"asiednie
kostki stykaj"a si"e bokami o tym samym kolorze, a na bokach kwadratu
jest kolor 0 (``bia"ly''). Zak"ladamy przy tym, "re 
ka"rdy wzorzec mo"rna wykorzysta"c dowolnie wiele razy, ale 
 nie mo"rna go
``obraca"c'' (tzn.~{\em up\/} jest zawsze g"orn"a kraw"edzi"a itd.).

Nale"ry udowodni"c, "re problem domina jest {\em NP\/}-zupe"lny.
Wskaz"owka~: zastosowa"c redukcj"e generyczn"a, tzn.~wychodz"ac
od dowolnej nie\-deter\-minis\-tycz\-nej 
maszyny Turinga dzia"laj"acej w czasie
wielomianowym.
\item \label{exact:cover}
Udowodni"c, "re nast"epuj"acy problem {\em dok"ladnego
pokrycia\/} (ang.~{\em exact cover\/}) jest  {\em NP\/}-zupe"lny.
Dana rodzina podzbior"ow $ \{ 1,2, \ldots , n \} $ (liczby
dane binarnie). Pytanie: czy istnieje podrodzina podzbior"ow
roz"l"acznych, kt"ore w sumie daj"a $ \{ 1,2, \ldots , n \} $.

Wskaz"owka~: wykorzysta"c zadanie~\ref{domino}.

\item \label{knapsack}
Udowodni"c, "re nast"epuj"acy problem {\em plecakowy\/}
(ang.~{\em knapsack problem}) jest  {\em NP\/}-zupe"lny.
Dane: liczby $n, m_1 , \ldots , m_k$ (binarnie). Pytanie:
czy istnieje podzbi"or zbioru $\{ m_1 , \ldots , m_k \}$
taki, "re $m_1 + \ldots + m_k = n$.
 
Wskaz"owka~: wykorzysta"c zadanie~\ref{exact:cover}.

\item Dowie"s"c, "re z"lo"renie dw"och funkcji obliczalnych 
w pami"eci (przestrzeni) logarytmicznej jest funkcj"a
obliczaln"a w pami"eci logarytmicznej.

\item Dowie"s"c, "re ka"rdy problem z klasy {\em NP} redukuje si"e do
problemu {\em 3-CNF~SAT}  w pami"eci logarytmicznej.


\end{enumerate}


\end{document}
