\documentclass[11pt]{article}
\usepackage[slovak]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{watermark}
\usepackage{framed}
\usepackage{shuffle}
\usepackage[pdftex]{graphicx}

\geometry{
  a4paper,
  top=25mm,
  bottom=18mm,
  right=21mm,
  left=22mm
}

\newcommand{\eps}{\varepsilon}
\newcommand{\fut}{\mathrm{Fut}}
\newlength{\enumshift}
\settowidth{\enumshift}{${}^*$}
\newcommand{\itemast}{\refstepcounter{enumi}\item[\theenumi.${}^*$\hspace{-\enumshift}]}
\def\domino#1#2{\begin{tabular}{|c|}\hline #1 \\\hline #2\\ \hline\end{tabular}}

\pagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}
\setlist{topsep=0pt}

\begin{document}
\begin{center}
{\Large\textbf{Sada úloh na cvičenie č. 13}}
\end{center}
\thispageheading{\vspace{-42pt}\begin{flushright}\begin{tabular}{l} Formálne jazyky a automaty (2) \\ Letný semester 2023/24 \end{tabular}\end{flushright}}

\begin{enumerate}
\item{Porovnajte triedu $\mathscr{L}_{detCF}$ s triedou všetkých jednoznačných bezkontextových jazykov.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že \emph{ľavým kvocientom} jazyka $L$ nad abecedou $\Sigma$ podľa slova $x \in \Sigma^*$ nazývame jazyk
\begin{displaymath}
x \backslash L = \{w \in \Sigma^* \mid xw \in L\}
\end{displaymath} 
a pre ľubovoľný jazyk $L' \subseteq \Sigma^*$ nazývame \emph{ľavým kvocientom} jazyka $L$ podľa jazyka $L'$ jazyk
\begin{displaymath}
L' \backslash L = \bigcup_{x \in L'} \left(x \backslash L\right) = \{w \in \Sigma^* \mid \exists x \in L': xw \in L\}.
\end{displaymath}  
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či je trieda $\mathscr{L}_{detCF}$ uzavretá na ľavý kvocient. Svoje tvrdenie dokážte.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že \emph{pravým kvocientom} jazyka $L$ nad abecedou $\Sigma$ podľa slova $x \in \Sigma^*$ nazývame jazyk
\begin{displaymath}
L / x = \{w \in \Sigma^* \mid wx \in L\}
\end{displaymath} 
a pre ľubovoľný jazyk $L' \subseteq \Sigma^*$ nazývame \emph{pravým kvocientom} jazyka $L$ podľa jazyka $L'$ jazyk
\begin{displaymath}
L / L' = \bigcup_{x \in L'} \left(L / x\right) = \{w \in \Sigma^* \mid \exists x \in L': wx \in L\}.
\end{displaymath}  
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či je trieda $\mathscr{L}_{detCF}$ uzavretá na pravý kvocient. Svoje tvrdenie dokážte.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že \emph{prefixovým uzáverom} jazyka $L$ nad abecedou $\Sigma$ nazývame jazyk 
\begin{displaymath}
\mathrm{pref}(L) = \{u \in \Sigma^* \mid \exists v \in \Sigma^*: uv \in L\}.
\end{displaymath}
Hovoríme, že trieda jazykov $\mathscr{L}$ je \emph{prefixovo uzavretá}, ak pre všetky $L \in \mathscr{L}$ je aj $\mathrm{pref}(L) \in \mathscr{L}$.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či je trieda $\mathscr{L}_{detCF}$ prefixovo uzavretá. Svoje tvrdenie dokážte.
}
\item{Zistite, či pre každý konečný jazyk $L$ existuje deterministický zásobníkový automat taký, že $N(A) = L$. Svoje tvrdenie dokážte.
}
\end{enumerate}

{\small
\leftbar
Pre účely nasledujúcich úloh označme ako $\mathscr{L}_{eDPDA}$ triedu všetkých jazykov akceptovaných deterministickými zásobníkovými automatmi \emph{prázdnym zásobníkom}.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či je trieda $\mathscr{L}_{eDPDA}$ uzavretá na zjednotenie. Svoje tvrdenie dokážte.
}
\item{Zistite, či je trieda $\mathscr{L}_{eDPDA}$ uzavretá na prienik. Svoje tvrdenie dokážte.
}
\item{Zistite, či je trieda $\mathscr{L}_{eDPDA}$ uzavretá na komplement. Svoje tvrdenie dokážte.
}
\end{enumerate}

\end{document}

