\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\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\kodTS#1{ \langle #1 \rangle}
\def\blank{{\bf B}}
\def\pseudoBlank{\overline{B}}

% FoJa Definicie KONIEC %


\begin{document}
	
\centerline{\Large\sc Sada úloh na cvičenie 9}
\bigskip
\hrule
\medskip

\begin{enumerate}

\item
Daná je gramatika $G = (\{S,A,B\},\{a,b,c\},P,S)$, kde 
\begin{eqnarray*}
P=\{ S &\to& Abc, \\
     A &\to& AB ~|~ Ba, \\
     B &\to& ab ~|~ aAb \}.
\end{eqnarray*}
Zostrojte pre túto gramatiku deterministický položkový automat.

\item
Daná je gramatika $G=(\{\sigma,\alpha,\beta\},\{a,b,c\},P,\sigma)$ s pravidlami
\begin{eqnarray*}
P=\{ \sigma &\to& \alpha c, \\
	\alpha &\to& \alpha b \beta\ |\ \beta b, \\
	\beta &\to& \alpha\beta\ |\ a \}.
\end{eqnarray*}
Je táto gramatika $LR(0)$? Ak nie, dokážte. Ak áno, 
zostrojte deterministický položkový automat a simulujte algoritmus shift-reduce na vstupe $abbabbaac$.

\item
Daná je gramatika $G=(N,\{a,(,),+\},P,S)$, kde $N=\{S,E,T\}$ a $P = $
\begin{eqnarray*}
P=\{ S  & \to & E, \\
     E & \to & T \mid E+T, \\
     T    & \to & a \mid (E) \}.
\end{eqnarray*}

Je táto gramatika  $LR(0)$? Ak áno, dokážte. Ak nie, nájdite 
vhodné slovo a demonštrujte, kedy pri parsovaní nastáva konfliktná situácia.

\item
Nech $G$ je bezkontextová gramatika $G = (\{S,A,B\},\{a,b,c\},P,S)$, kde 
\begin{eqnarray*}
P=\{ S &\to& Abc, \\
     A &\to& AB ~|~ Ba, \\
     B &\to& ab ~|~ aAb \}.
\end{eqnarray*}
Uvažujme vetnú formu $AaABbbc$. Pre túto vetnú formu nájdite {\em handle}, všetky {\em životaschopné prefixy} a pre každý z nich všetky
{\em platné LR-elementy}.

\item 
Podobne, ako $LR(0)$ môžeme definovať aj $RL(0)$ gramatiky (teda vstup čítame sprava a hľadáme ľavé krajné odvodenie). Analogicky k $LR(0)$ gramatikám definujte všetky potrebné pojmy, ktoré budete pri definovaní $RL(0)$ gramatík potrebovať.

\item
Rozhodnite a dokážte, či platia nasledovné tvrdenia:
\begin{enumerate}
\item Každá jednoznačná bezkontextová gramatika je $LR(0)$ gramatika.
\item Každá $LR(0)$ gramatika je jednoznačná bezkontextová gramatika.
\end{enumerate}


\end{enumerate}

\end{document}
