\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 č. 12}}
\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{Uvažujme jednoznačnú bezkontextovú gramatiku $G = (N,T,P,\sigma)$ s $N = \{\sigma,\alpha,\beta\}$, $T = \{a,b\}$~a
\begin{align*}
P=\{ \sigma & \to \alpha \beta ~|~ \eps \\
     \alpha & \to a\alpha ~|~ a \\
     \beta & \to \beta bb ~|~ b \}.
\end{align*}
Nájdite \uv{handle} a všetky životaschopné prefixy v nasledujúcich pravých vetných formách~v~$G$:
\begin{enumerate}[label=\alph*)]
\item{$w = aaaabbb$;
}
\item{$w = \alpha\beta bbbb$.
} 
\end{enumerate}
}
\item{Uvažujme jednoznačnú bezkontextovú gramatiku $G = (N,T,P,\sigma)$ s $N = \{\sigma,\alpha,\beta\}$, $T = \{a,b,c\}$ a
\begin{align*}
P=\{ \sigma & \to \alpha c \alpha c \beta ~|~ cc \\
     \alpha & \to a\alpha b ~|~ ab \\
     \beta & \to b \beta a ~|~ ba \}.
\end{align*}
Nájdite \uv{handle} a všetky životaschopné prefixy v nasledujúcich pravých vetných formách~v~$G$:
\begin{enumerate}[label=\alph*)]
\item{$w = aabbcabcbbbaaa$;             
}
\item{$w = \alpha caa\alpha bbcba$.
} 
\end{enumerate} 
}
\item{Nech $G = (N,T,P,\sigma)$ je bezkontextová gramatika s $N = \{\sigma,\alpha,\beta\}$, $T = \{a,b,c\}$ a 
\begin{align*}
P=\{ \sigma & \to a\alpha b\alpha ~|~ b\beta \\
     \alpha & \to bc\alpha ~|~ c\beta \\
     \beta & \to c\beta a ~|~ b \}.
\end{align*}
Zostrojte nedeterministický a deterministický položkový automat pre gramatiku $G$ a zistite, či je táto gramatika
$\mathrm{LR}(0)$. Ak áno, zvoľte si vhodný vstup a odsimulujte na ňom algoritmus \uv{posuň a redukuj}.
Ak nie, nájdite slovo, pri spracovaní ktorého by nastal konflikt.
}
\item{Nech $G = (N,T,P,\sigma)$ je bezkontextová gramatika s $N = \{\sigma,\alpha,\beta\}$, $T = \{a,b\}$ a 
\begin{align*}
P=\{ \sigma & \to \alpha b ~|~ a \\
     \alpha & \to \alpha b \beta ~|~ a \beta b \\
     \beta & \to \alpha \beta ~|~ b \}.
\end{align*}
Zostrojte nedeterministický a deterministický položkový automat pre gramatiku $G$ a zistite, či je táto gramatika
$\mathrm{LR}(0)$. Ak áno, zvoľte si vhodný vstup a odsimulujte na ňom algoritmus \uv{posuň a redukuj}.
Ak nie, nájdite slovo, pri spracovaní ktorého by nastal konflikt.
}
\item{\emph{Bez použitia deterministických zásobníkových automatov} (ale s možnosťou odvolávania sa na~algoritmus \uv{posuň a redukuj}) dokážte,
že každý jazyk $L$ generovaný $\mathrm{LR}(0)$ gramatikou je bezprefixový -- ak teda $L \subseteq \Sigma^*$ a $u \in L$, nemôže existovať žiadne $v \in \Sigma^+$ také, že $uv \in L$.  
}
\item{Nech $G$ je redukovaná a súčasne \uv{bezepsilonová} bezkontextová gramatika.
Dokážte, že gramatika $G$ je $\mathrm{LR}(0)$ práve vtedy, keď sú splnené nasledujúce podmienky:
\begin{itemize}
\item[$(i)$]{Počiatočný neterminál $\sigma$ sa nevyskytuje na pravej strane žiadneho pravidla -- to znamená, že 
$P \subseteq N \times {((N - \{\sigma\}) \cup T)}^*$.
}
\item[$(ii')$]{Ak je pre nejaký životaschopný prefix $x$ v $G$ platná úplná $\mathrm{LR}(0)$ položka,
tak pre $x$ nie je platná \emph{žiadna iná} $\mathrm{LR}(0)$ položka. 
}
\end{itemize} 
(Podmienka $(ii')$ je sprísnením podmienky $(ii)$ z~definície $\mathrm{LR}(0)$ gramatiky.)\goodbreak
}
\item{Nájdite 
\begin{enumerate}[label=\alph*)]
\item{redukovanú
}
\item{\uv{bezepsilonovú}
}
\end{enumerate}
$\mathrm{LR}(0)$ gramatiku, v~ktorej je pre nejaký životaschopný prefix $x$ platná úplná $\mathrm{LR}(0)$ položka a~súčasne $\mathrm{LR}(0)$
položka so symbolom $\bullet$ pred neterminálom.
}
\item{Definujte $\mathrm{RL}(0)$ gramatiky, ktoré sú obdobou $\mathrm{LR}(0)$ gramatík, ale sú určené na spracovanie algoritmom \uv{posuň a redukuj}
čítajúcim vstup \emph{sprava doľava} a konštruujúcim \emph{ľavé krajné odvodenie}.
Nájdite príklad \emph{gramatiky}, ktorá nie je $\mathrm{LR}(0)$, ale je $\mathrm{RL}(0)$.
}
\end{enumerate}

\end{document}

