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

% FoJa Definicie ZACIATOK %
\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\Ldpda{\mathscr{L}_{\it DPDA}}
\def\Ledpda{\mathscr{L}_{\it eDPDA}}

\def\kodTS#1{ \langle #1 \rangle}
\def\blank{{\bf B}}
\def\pseudoBlank{\overline{B}}

\def\domino#1#2{\begin{tabular}{|c|}\hline #1 \\\hline #2\\ \hline\end{tabular}}

\def\to{\rightarrow}
\def\compStep#1{\vdash_{#1}}
\def\compStepIt#1{\vdash^*_{#1}}
% FoJa Definicie KONIEC %


\begin{document}

\centerline{\Large\sc Sada úloh na cvičenie 4}
\bigskip
\hrule
\bigskip

\centerline{\bf Definície:}

{\bf Pravý kvocient:} Nech $L_1$ a $L_{2}$ sú jazyky. Definujeme

\begin{displaymath}
L_1 / L_2 = \{ w \in \Sigma_{L_1}^* ~|~ (\exists u \in L_2) ~ wu \in L_1 \}.
\end{displaymath}

Túto operáciu nazývame pravý kvocient.

\bigskip
\hrule
\bigskip

\begin{enumerate}
	
\item
Nech $G=(N,T,P,\sigma)$ je bezkontextová gramatika, kde $N=\{\alpha,\beta,\sigma\}$, $T=\{a,b\}$ a
\begin{eqnarray*}
	P = \{  \sigma &\to& \alpha\beta ~|~ \beta\alpha \\
	\beta &\to& \alpha\sigma ~|~ \sigma b ~|~ bab \\
	\alpha &\to& \beta \sigma \beta ~|~ \alpha\sigma a ~|~ aa 
	\}.
\end{eqnarray*}
Preveďte túto gramatiku do Greibachovej normálneho tvaru.

\item
Nech $G=(N,T,P,\sigma)$ je bezkontextová gramatika, kde $N=\{\sigma, \alpha\}$, $T=\{a,b,c\}$ a
\begin{eqnarray*}
	P = \{  \sigma &\to& \sigma a \sigma b  ~|~ \alpha b ~|~ c \\
			\alpha &\to& \alpha a \sigma ~|~ \sigma a \alpha b ~|~ a
	\}.
\end{eqnarray*}
K danej gramatike zostrojte  PDA A, ktorý neobsahuje prechody na epsilon a má iba jeden stav a platí $N(A) = L(G)$.


\item
Nech $L = \{ b^{2k+1}a^{n^2}b^{2l+1} ~|~ n,k,l \in \N^+ \}$. Pomocou Ogdenovej lemmy dokážte, že jazyk $L$ nie je bezkontextový.


\item
Nech $L = \{ a^{n}d^{3k+2}b^{n}d^{7l+1}c^{n} ~|~ n,k,l \in \N^+ \}$. Pomocou Ogdenovej lemmy dokážte, že jazyk $L$ nie je bezkontextový.

\item
Dokážte vetu o lineárnom priestore. Teda dokážte, že ak platí $L \in NSPACE(O(n))$, tak $L \in \Lecs$. Potrebnú konštrukciu LBA spravte poriadne formálne. Jej správnosť slušne slovne zdôvodnite.

	
\item
Rozhodnite a dokážte či je trieda $\Lecs$ uzavretá na pravý kvocient.

\item
{\bf Pre náročnejších:}
Uvažujme problém: pre daný orientovaný graf $G$ a dva jeho vrcholy $u$ a $v$ rozhodnúť, že medzi týmito vrcholmi {\tt neexistuje} cesta. 
Rozhodnite a dokážte, či je tento problém riešiteľný na nedeterministickom turingovom stroji v logaritmickom priestore. Presnejšie, uvažujme nejaké vhodné kódovanie grafov nad abecedou $\{0,1,\#\}$, ktorého veľkosť pre graf s $N$ vrcholmi sa zmestí do $O(N^2)$. Možným vhodným kódovaním je uvažovať kód grafu ako zoznam jeho hrán. Prípadný stroj by nemal použiť viac ako $O(\log N)$ políčok pracovnej pásky.



\end{enumerate}

\end{document}
