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

\newcommand{\eps}{\varepsilon}

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

\pagestyle{empty}
\setlength{\parindent}{0pt}

\newenvironment{modenumerate}
  {\enumerate\setupmodenumerate}
  {\endenumerate}

\newif\ifmoditem
\newcommand{\setupmodenumerate}{%
  \global\moditemfalse
  \let\origmakelabel\makelabel
  \def\moditem##1{\global\moditemtrue\def\mesymbol{##1}\item}%
  \def\makelabel##1{%
    \origmakelabel{##1\ifmoditem\rlap{\mesymbol}\fi\enspace}%
    \global\moditemfalse}%
}

\begin{document}
\begin{center}
{\Large\textbf{Štvrtá sada bodovaných domácich úloh}}
\end{center}
\thispageheading{\vspace{-42pt}\begin{flushright}\begin{tabular}{l} Formálne jazyky a automaty (2) \\ Letný semester 2023/24 \end{tabular}\end{flushright}}

Úlohy tejto sady je potrebné odovzdať \textbf{do stredy 15. mája 2024, 12:45} do krabice,
ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254), prípadne osobne na cvičeniach.

{\small
\leftbar
\emph{Zásobníkový prekladač} možno opísať ako a-prekladač, ktorý má navyše prístup k zásobníku: ide o~osmicu
$M = (K,\Sigma_1,\Sigma_2,\Gamma,H,q_0,Z_0,F)$, kde $K$ je konečná množina stavov, $\Sigma_1$ je vstupná abeceda,
$\Sigma_2$ je výstupná abeceda, $\Gamma$ je zásobníková abeceda, $H \subseteq K \times \Sigma_1^* \times \Sigma_2^* \times \Gamma \times K \times \Gamma^*$ je \emph{konečná} množina prechodov,
$q_0 \in K$ je počiatočný stav, $Z_0 \in \Gamma$ je počiatočný zásobníkový symbol a $F \subseteq K$ je množina akceptačných stavov.

Prechod $(p,x,y,Z,q,\gamma)$ interpretujeme tak, že prekladač $M$ v stave $p$ so symbolom $Z$ na vrchu zásobníka môže zo vstupu prečítať $x$, na výstup zapísať $y$ a prejsť tak do stavu $q$,
pričom symbol $Z$ na vrchu zásobníka je nahradený slovom $\gamma$.

\emph{Konfiguráciou} zásobníkového prekladača $M$ nazveme štvoricu $(q,u,v,\gamma) \in K \times \Sigma_1^* \times \Sigma_2^* \times \Gamma^*$. Zložky tejto štvorice postupne reprezentujú
stav prekladača, nedočítanú časť vstupného slova, doposiaľ zapísanú časť výstupného slova a obsah zásobníka s dnom naľavo.

\emph{Krok výpočtu} zásobníkového prekladača $M$ je binárna relácia $\vdash_M$ na jeho konfiguráciách taká, že pre~\mbox{$p,q \in K$}, $u,u' \in \Sigma_1^*$, $v,v' \in \Sigma_2^*$ a $\gamma,\gamma' \in \Gamma^*$ je
$(p,u,v,\gamma) \vdash_M (q,u',v',\gamma')$ práve vtedy, keď existujú $x \in \Sigma_1^*$, $y \in \Sigma_2^*$, $\alpha,\beta \in \Gamma^*$ a $Z \in \Gamma$ také, že
$u = xu'$, $v' = vy$, $\gamma = \alpha Z$, $\gamma' = \alpha\beta$ a $(p,x,y,Z,q,\beta) \in H$.
Ak nehrozí nedorozumenie, môžeme namiesto $\vdash_M$ písať len $\vdash$.

\emph{Preklad} realizovaný zásobníkovým prekladačom $M$ je relácia $\Pi(M) \subseteq \Sigma_1^* \times \Sigma_2^*$ definovaná ako
\begin{displaymath}
\Pi(M) = \{(u,v) \in \Sigma_1^* \times \Sigma_2^* \mid \exists q \in F~\exists \gamma \in \Gamma^*\colon (q_0,u,\eps,Z_0) \vdash_M^* (q,\eps,v,\gamma)\}.
\end{displaymath}      

\emph{Obraz jazyka $L \subseteq \Sigma_1^*$ pri zobrazení zásobníkovým prekladačom $M$} definujeme ako
\begin{displaymath}
M(L) = \{v \in \Sigma_2^* \mid \exists u \in L~\exists q \in F~\exists \gamma \in \Gamma^*\colon (q_0,u,\eps,Z_0) \vdash_M^* (q,\eps,v,\gamma)\}.
\end{displaymath}

Podobne ako v prípade a-prekladačov nazveme zásobníkový prekladač $M = (K,\Sigma_1,\Sigma_2,\Gamma,H,q_0,Z_0,F)$ \emph{$1$-ohraničeným},
ak $H \subseteq K \times (\Sigma_1 \cup \{\eps\}) \times (\Sigma_2 \cup \{\eps\}) \times \Gamma \times K \times \Gamma^*$. 
\endleftbar  
}

\begin{enumerate}
\item{Zistite, či ku každému zásobníkovému prekladaču $M$ existuje $1$-ohraničený zásobníkový prekladač $M'$ taký, že $\Pi(M') = \Pi(M)$.
}
\item{Porovnajte triedu všetkých prekladov realizovaných zásobníkovými prekladačmi s triedou všetkých prekladov realizovaných a-prekladačmi.
}
\item{Porovnajte triedu všetkých prekladov realizovaných zásobníkovými prekladačmi s triedou všetkých prekladov realizovaných jednoduchými prekladovými schémami.
}
\end{enumerate}
Prípadné konštrukcie prekladačov alebo prekladových schém zapisujte formálne; ich správnosť stačí zdôvodniť slovne.
\end{document}

