\documentclass[a4paper]{article}
\usepackage[slovak]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{shuffle}
\usepackage{color}
\usepackage{multicol}
\def\skok{{}{\hspace{1cm}}}
\RequirePackage{amssymb}
\usepackage{ wasysym }

% FoJa Definicie ZACIATOK %
\def\eps{\varepsilon}
\def\N{\mathbb{N}}
\def\Lcf{\mathscr{L}_{\it CF}}
\def\R{{\cal R}}
\def\Lre{\mathscr{L}_{\it RE}}
\def\Lrec{\mathscr{L}_{\it rec}}
\def\Lecs{\mathscr{L}_{\it ECS}}
\def\Ldpda{\mathscr{L}_{\it DPDA}}
\def\Ledpda{\mathscr{L}_{\it eDPDA}}

\def\kodTS#1{ \langle #1 \rangle}
\def\blank{{\bf B}}
\def\pseudoBlank{\overline{B}}

\def\domino#1#2{\begin{tabular}{|c|}\hline #1 \\\hline #2\\ \hline\end{tabular}}

\def\to{\rightarrow}
\def\compStep#1{\vdash_{#1}}
\def\compStepIt#1{\vdash^*_{#1}}
% FoJa Definicie KONIEC %


\begin{document}

\centerline{\Large\sc Sada úloh na cvičenie 3}
\bigskip
\hrule
\bigskip

\centerline{\bf Poznámka:}
Ak zadanie požaduje skonštruovať rozšírenú kontextovú gramatiku, môžete skonštruovať \uv{takmer rozšírenú kontextovú gramatiku} ako sme si ukazovali na cvičeniach. Teda frázovú gramatiku, pre ktorú existuje pevná konštanta $k$ taká, že v každom odvodení sa použijú \uv{skracujúce} pravidlá najviac $k$ krát. Túto vlastnosť skonštruovanej gramatiky treba samozrejme dokázať.

\bigskip

\centerline{\bf Definície:}
{\bf Shuffle:} Nech $ L_1, L_2 $ sú ľubovolné jazyky. Operáciu $\shuffle$ na jazykoch definujeme nasledovne:

\begin{displaymath}
L_1 \shuffle L_2 = \{ u_1 v_1 \ldots u_n v_n ~|~ n \geq 1 ;~ u_1, \ldots, u_n \in \Sigma_{L_1}^* ;~ v_1, \ldots, v_n \in \Sigma_{L_2}^* ;~ u_1 \dots u_n \in L_1 ;~ v_1 \ldots v_n \in L_2 \}
\end{displaymath}

Operáciu $ \shuffle $ nazývame \uv{shuffle}.

\bigskip
\hrule
\bigskip

\begin{enumerate}

\item
Nech $ \Sigma $ je abeceda, nech $ \Sigma_1 \subseteq \Sigma $, $ \Sigma_2 \subseteq \Sigma $, $ R \subseteq \Sigma \times \Sigma $ je relácia na $ \Sigma $ a $ L \subseteq \Sigma^* $ je jazyk definovaný nasledovne. Slovo $ w \in L $ práve vtedy keď platí $ w=\varepsilon $ alebo $ w=a_1 \ldots a_n $ a sú splnené nasledovné podmienky:

\begin{enumerate}[label=(\roman*)]
\item $ a_1 \in \Sigma_1 $
\item $ a_n \in \Sigma_2 $
\item $ a_i R a_{i+1} $ pre $ 0 \leq i < n $
\end{enumerate}

Potom $ L \in \mathscr{R} $. Poriadne dokážte!

\item
Zostrojte rozšírenú kontextovú gramatiku pre jazyk $L = \{a^nb^{n^2}~|~ n \in \N \}$. Správnosť vašej konštrukcie poriadne zdôvodnite.

\item Zostrojte LBA, ktorý akceptuje jazyk $L = \{a^nb^{2^n} ~|~ n \in \N \}$. Správnosť vašej konštrukcie poriadne zdôvodnite.

\item
Formálne definujte (klasické 4 definície) viacpáskové\footnote{Každý viacpáskový LBA má fixný počet pások.} LBA a porovnajte ich silu s jednopáskovými LBA. Vaša definícia by mala zabezpečiť, že vstup bude na začiatku na prvej páske a že vami definované viacpáskové LBA bude môcť použiť na každej zo svojich pások najviac toľko políčok, koľko je dĺžka vstupu.

\item
Formálne dokážte, že kontextové gramatiky, ktorých pravidlá navyše spĺňajú podmienku, že ich pravidlá majú na ľavej strane iba neterminály sú normálnym tvarom kontextových gramatík. Formálne má množina pravidel $P$ spĺňať nasledovné: (1) $(\forall u \rightarrow v \in P)~|u| \leq |v|$ (2) $ P \subseteq_{kon} N^+ \times (N \cup T)^+ $

\item
Pre daný LBA $A_1$ zostrojte LBA $A_2$, ktorý na vstupe $ w \in \{a\}^* $ generuje všetky konfigurácie  $A_1$ na dĺžke vstupu $ |w| $  v lexikografickom poradí. Po vygenerovaní konfigurácie má váš LBA prejsť do nejakého špeciálneho stavu. Z neho potom pokračuje generovaním ďalšej  konfigurácie . V momente, keď váš LBA vygeneruje poslednú konfiguráciu, prejde do iného špeciálneho stavu a zastane. Už vygenerované konfigurácie si netreba nikde pamätať. {\it Hint:} myslite na to, že do reprezentácie konfigurácie potrebujete zakomponvať aj informáciu o pozícii hlavy a stave $A_1$. To sa dá napríklad pomocou viacstopej pásky.

\item
Dokážte, že trieda $ \Lecs $ je uzavretá na operáciu shuffle.


\item
Definujme operáciu $\parallel$ na jazykoch nasledovne:

\begin{displaymath}
L_1 \parallel L_2 = \{ w_1w_2 ~|~ w_1 \in L_1 ;~ w_2 \in L_2 ;~ |w_1| = |w_2| \}.
\end{displaymath}

Rozhodnite a dokážte, či je trieda $ \Lecs $ uzavretá na operáciu $\parallel$.	



\end{enumerate}

\end{document}
