\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 8}
\bigskip
\hrule
\medskip

\centerline{\bf Definície}
\begin{itemize}
	\item $ \mathscr{L}_{\Pi}$ je trieda prekladov daných jednoduchými syntaxou riadenými prekladovými schémami
\end{itemize}

\medskip
\hrule
\bigskip

\begin{enumerate}

\item
Daná je bezkontextová gramatika $G = (\{\sigma,\alpha,\beta,\gamma\},\{a,b,c,d\},P,\sigma)$ s
pravidlami:
\begin{eqnarray*}
P = \{ & \sigma & \rightarrow \alpha\sigma ~|~ \beta\gamma \\
       & \alpha & \rightarrow \alpha\alpha ~|~ \gamma\beta ~|~ a \\
       & \beta  &  \rightarrow \beta\gamma ~|~ b ~|~ d\\
       & \gamma & \rightarrow \gamma\beta ~|~ c ~|~ a \}
\end{eqnarray*}
Pomocou algoritmu CYK zistite, či slovo $aadada$ patrí do $L(G)$. Očakáva sa, že  skonštruujte všetky množiny $N_{i,j}$.


\item Dokážte alebo vyvráťte nasledovné tvrdenie. Trieda prekladov daných jednoduchými syntaxou riadenými prekladovými schémami je uzavretá na reverz. Presnejšie, ak $L(\Pi) \in \mathscr{L}_{\Pi}$, tak aj $L(\Pi)^R = \{(u^R,v^R)~ |~ (u,v) \in L(\Pi)  \}~ \in \mathscr{L}_{\Pi}$.

\item   Dokážte alebo vyvráťte nasledovné tvrdenie. Trieda prekladov daných jednoduchými syntaxou riadenými prekladovými schémami je uzavretá na zjednotenie. Presnejšie, ak $L(\Pi_1) \in \mathscr{L}_{\Pi}$ a $L(\Pi_2) \in \mathscr{L}_{\Pi}$, tak $L(\Pi_1) \cup L(\Pi_2) \in  \mathscr{L}_{\Pi}$.

\item
Vo vašom obľúbenom programovacom jazyku naprogramujte program, ktorý na vstupe berie bezkontextovú gramatiku $ G $ v prísnom Chomského normálnom tvare (zvoľte vhodné kódovanie vstupu) a dve množiny neterminálov ($ N_1, N_2 $) a na výstupe vracia množinu $ M = \{ \alpha ~|~ \exists \alpha_1 \in N_1, \alpha_2 \in N_2 : \alpha \rightarrow \alpha_1 \alpha_2 \in P_G \} $. Váš program by mal fungovať ako konzolová aplikácia čítajúca vstup v nejakom formáte zo štandardného vstupu a vypisujúca výsledok na štandardný výstup. Ak máte chuť spraviť klikaciu okienkovú aplikáciu, môžete, ale konzolová aplikácia je minimum.

\item
Máme danú gramatiku $G = (\{Z,E,T\},\{x,+,(,)\},P,Z)$, kde
\begin{eqnarray*}
	P=\{ Z &\to& (E),\\
	E &\to& x ~|~ x + T ~|~ T,\\
	T &\to& x ~|~ (E)\}.
\end{eqnarray*}
Určite precedenčné relácie $\gtrdot$,$\doteq$ a $\lessdot$
a na základe nich rozhodnite, či je táto gramatika
jednoducho precedenčná.

\item
Máme danú gramatiku $ G = (\{ \sigma,\alpha \}, \{a,b,c \},P, \sigma) $, kde 
\begin{eqnarray*}
	P=\{ \sigma &\to& a \alpha a,\\
	\alpha &\to& \alpha bc ~|~ c\}.
\end{eqnarray*}
Určite precedenčné relácie $\gtrdot$,$\doteq$ a $\lessdot$
a na základe nich rozhodnite, či je táto gramatika
jednoducho precedenčná.


\end{enumerate}

\end{document}
