\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 č. 11}}
\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{Nech $G = (N,T,P,\sigma)$ je bezkontextová gramatika s $N = \{\sigma,\alpha,\beta\}$, $T = \{a,b,c,d\}$ a
\begin{align*}
P=\{ \sigma & \to aa\sigma ~|~ a\alpha \\
     \alpha & \to \sigma b ~|~ \alpha b \beta ~|~ c \\
     \beta & \to d\beta ~|~a \}.
\end{align*}
Vypočítajte relácie $\doteq$, $\lessdot$ a $\gtrdot$ pre gramatiku $G$ a zistite, či je gramatika $G$
jednoducho precedenčná. Ak áno, odsimulujte algoritmus \uv{posuň a redukuj} na slove $abccdb$.
}
\item{Nech $G = (N,T,P,\sigma)$ je bezkontextová gramatika s $N = \{\sigma,\alpha,\beta\}$, $T = \{a,b,c,d\}$ a
\begin{align*}
P=\{ \sigma & \to a\alpha b ~|~ c \\
     \alpha & \to b\beta \\
     \beta & \to c\beta ~|~ d \}.
\end{align*}
Vypočítajte relácie $\doteq$, $\lessdot$ a $\gtrdot$ pre gramatiku $G$ a zistite, či je gramatika $G$
jednoducho precedenčná. Ak áno, odsimulujte algoritmus \uv{posuň a redukuj} na slove $abccdb$. 
}
\item{Nech $G = (N,T,P,\sigma)$ je bezkontextová gramatika s $N = \{\sigma,\alpha,\beta\}$, $T = \{a,b,c,d\}$ a
\begin{align*}
P=\{ \sigma & \to b\alpha ~|~ \beta d \\
     \alpha & \to a ~|~ ab \\
     \beta & \to \beta c ~|~ ab \}.
\end{align*}
Vypočítajte relácie $\doteq$, $\lessdot$ a $\gtrdot$ pre gramatiku $G$ a zistite, či je gramatika $G$
jednoducho precedenčná. Ak áno, odsimulujte algoritmus \uv{posuň a redukuj} na slove $abccdb$. 
}
\item{Zistite, či existuje:
\begin{enumerate}[label=\alph*)]
\item{Jednoducho precedenčná gramatika $G$ taká, že $L(G) = \{a^n b^n \mid n \in \mathbb{N}\}$.
}
\item{Jednoducho precedenčná gramatika $G$ taká, že $L(G) = \{a^n b^n \mid n \in \mathbb{N} - \{0\}\}$.
}
\end{enumerate}
Svoje tvrdenia dokážte.
}
\item{Nech $\Sigma = \{a,b\}$. Nájdite bezkontextový jazyk $L \subseteq \Sigma^+$, ktorý nemožno vygenerovať žiadnou jednoducho precedenčnou gramatikou.
}
\item{Musí byť každý konečný jazyk neobsahujúci $\eps$ generovaný nejakou jednoducho precedenčnou gramatikou?
}
\item{Pre ľubovoľné $m,n \in \mathbb{N} - \{0\}$ formálne zadefinujte -- vrátane variantov relácií $\doteq$, $\lessdot$ a $\gtrdot$ -- $(m,n)$-precedenčné 
gramatiky, ktoré sú založené na reláciách medzi dvojicami podslov, kde \uv{ľavé} je dĺžky $m$ a \uv{pravé} je dĺžky $n$.
Nájdite príklad bezkontextovej \emph{gramatiky}, ktorá nie je jednoducho precedenčná, ale je $(2,2)$-precedenčná.  
}
\item{Nájdite príklad bezkontextovej gramatiky $G = (N,T,P,\sigma)$ takej, že všetky dvojice terminálov
$(a,b) \in T^2$ sú súčasne vo všetkých troch reláciách $\doteq$, $\lessdot$ a $\gtrdot$, alebo ukážte,
že taká gramatika neexistuje.
}
\end{enumerate}

\end{document}

