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

\pagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}
\setlist{topsep=0pt}

\begin{document}
\begin{center}
{\Large\textbf{Sada úloh na cvičenie č. 4}}
\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{Zistite, či je jazyk $L = \{a^i b^j c^k \mid i,j,k \in \mathbb{N};~j = \max\{i,k\}\}$ bezkontextový. Svoje tvrdenie dokážte.
}
\item{Zistite, či je jazyk $L = \{a^i b^j c^k \mid i,j,k \in \mathbb{N};~i \neq j ~\land~ j \neq k ~\land~ i \neq k\}$ bezkontextový. Svoje tvrdenie dokážte.
}
\end{enumerate}

{\small
\leftbar
Bezkontextová gramatika $G = (N,T,P,\sigma)$ je \emph{lineárna}, ak $P \subseteq N \times (T^* \cup T^* N T^*)$.
Jazyk $L$ je \emph{lineárny}, ak existuje lineárna gramatika $G$ taká, že $L(G) = L$.
Triedu všetkých lineárnych jazykov označujeme $\mathscr{L}_{lin}$.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Porovnajte triedu $\mathscr{L}_{lin}$ s triedami $\mathscr{R}$ a $\mathscr{L}_{CF}$.
}
\item{Nech $G = (N,T,P,\sigma)$ je bezkontextová gramatika s $N = \{\sigma,\alpha\}$, $T = \{a,b\}$ a
\begin{align*}
P=\{ \sigma & \to \sigma b ~|~ \alpha b ~|~ a\alpha b \\
     \alpha & \to \sigma \alpha a ~|~ \alpha a ~|~ b\}.
\end{align*}
Štandardnou konštrukciou zostrojte gramatiku $G'$ v Greibachovej normálnom tvare takú, že $L(G') = L(G) - \{\eps\}$.
}
\end{enumerate}

{\small
\leftbar
Bezkontextová gramatika $G = (N,T,P,\sigma)$ je v \emph{kvadratickom Greibachovej normálnom tvare}, ak 
\begin{displaymath}
P \subseteq N \times (T \cup TN \cup TNN).
\end{displaymath}  
\endleftbar  
}

\begin{enumerate}[resume]
\item{Dokážte, že ku každej bezkontextovej gramatike $G$ existuje bezkontextová gramatika $G'$ v kvadratickom Greibachovej normálnom tvare
taká, že $L(G') = L(G) - \{\eps\}$.
}
\end{enumerate}

{\small
\leftbar
Bezkontextová gramatika $G = (N,T,P,\sigma)$ je v \emph{operátorovom normálnom tvare}, ak sa na pravej strane žiadneho pravidla nevyskytujú dva po sebe idúce neterminály --
čiže ak 
\begin{displaymath}
P \subseteq N \times ((N \cup T)^* - (N \cup T)^* NN (N \cup T)^*).
\end{displaymath}
\endleftbar  
}

\begin{enumerate}[resume]
\item{Dokážte, že ku každej bezkontextovej gramatike $G$ existuje bezkontextová gramatika $G'$ v operátorovom normálnom tvare taká, že $L(G') = L(G)$.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že pre každú bezkontextovú gramatiku $G$ v Greibachovej normálnom tvare možno štandardnú konštrukciu ekvivalentného zásobníkového automatu modifikovať tak,
aby sme získali \uv{bezepsilonový} zásobníkový automat $A$ taký, že $N(A) = L(G)$; \uv{bezepsilonovosť} zásobníkového automatu $A = (K,\Sigma,\Gamma,\delta,q_0,Z_0,F)$
tu znamená, že pre všetky $q \in K$ a $Z \in \Gamma$ je $\delta(q,\eps,Z) = \emptyset$. 

V dôsledku toho pre každý bezkontextový jazyk $L$ existuje \uv{bezepsilonový} zásobníkový automat taký, že $N(A) = L - \{\eps\}$.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Dokážte, že pre každý bezkontextový jazyk $L$ existuje \uv{bezepsilonový} zásobníkový automat taký, že $L(A) = L$. 
}
\item{Zostrojte lineárne ohraničený automat, ktorý na vstupe $a^n$ pre $n \in \mathbb{N}$ postupne v lexikografickom usporiadaní \uv{generuje} všetky slová $u \in \{a,b\}^*$ dĺžky $n$, pričom po \uv{vygenerovaní} každého slova
sa dostane do nejakého špeciálneho stavu a po \uv{vygenerovaní} posledného slova sa zastaví.
}
\end{enumerate}

\end{document}

