\documentclass[a4paper]{article}
\usepackage[slovak]{babel}
%\usepackage[utf8]{inputenc}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{mathcomp}
\usepackage{shuffle}
\usepackage{listings}
\usepackage{color}
\usepackage{multicol}
\def\skok{{}{\hspace{1cm}}}
\RequirePackage{amssymb}
\usepackage{ wasysym }
\def\eps{\varepsilon}
\def\then{\Rightarrow}
\parindent 0pt
\def\skok{{}{\hspace{1cm}}}
\RequirePackage{amssymb}



\def\then{\Rightarrow}
\parindent 0pt

\def\skok{{}{\hspace{1cm}}}
\RequirePackage{amssymb}

\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}}

\begin{document}

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

Pripomeňme si, že $\Ldpda$ je trieda jazykov, ktoré je možno akceptovať deterministickým zásobníkovým automatom akceptujúcim akceptačným stavom. $\Ledpda$ je trieda jazykov, ktoré je možno akceptovať deterministickým zásobníkovým automatom prázdnou pamäťou.

\medskip

Pripomíname, že pokiaľ nie je uvedené inak, tak konštrukcie v dôkazoch treba spraviť formálne a ich správnosť slovne zdôvodniť.
\bigskip
\hrule
\medskip

\begin{enumerate}

\item
Pre danú inštanciu PKP uvažujme jazyky $L_X,L_Y$ a $L_{XY}$. Môžete použiť
definíciu zo skrípt alebo tú z prednášky (definíciu nájdete aj v 5. prezentačnej sade). Ktoré z nich patria do triedy $\Ldpda$? Váš záver dokážte.

\item
Dokážte alebo vyvráťte: $L = \{ a^nb^mc^k ~|~ n,m,k \ge 0, n \neq m \lor n \neq k  \} \in \Ldpda$. 

\item 
Definujeme $ L_1 =\{ w c w^R ~|~ w \in \{a,b\}^*\}$. Rozhodnite, či $L_1 \in \Ledpda$. Rozhodnite, či $L_1 \in \Ldpda$.

\item 
Definujeme $ L_1 =\{ ba^nb^n ~|~  n \geq 0\} \cup \{ bba^nb^{2n} | n \geq 0 \}$. Rozhodnite, či $L_1 \in \Ledpda$. Rozhodnite, či $L_1 \in \Ldpda$.

\item
Povieme, že $L$ je {\it bezprefixový}, ak pre každé $w\in L$ platí, že $w$ nie je prefixom iného slova z $L$. Dokážte, že jazyk $L$ patrí do $\Ledpda$ vtedy a len vtedy, ak je bezprefixový a zároveň patrí do $\Ldpda$.


\item
Porovnajte triedy $\R$ a $\Ledpda$ (ukážte, či sú rovnaké, jedna podmnožina druhej alebo neporovnateľné).


\item {\bf Pre náročnejších:} Definujme $Pref(L) = \{u  ~|~ \exists v \in \Sigma^*, uv \in L\}$. Rozhodnite, či:
\begin{enumerate}
	\item $\Ledpda$ je uzavretá na $Pref(L)$.
	\item $\Ldpda$ je uzavretá na $Pref(L)$.
\end{enumerate}
Vaše tvrdenia poriadne zdôvodnite.


\end{enumerate}

\end{document}
