\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 č. 8}}
\end{center}
\thispageheading{\vspace{-42pt}\begin{flushright}\begin{tabular}{l} Formálne jazyky a automaty (2) \\ Letný semester 2023/24 \end{tabular}\end{flushright}}

{\small
\leftbar
Nech $(\Delta,f,g)$ s $\Delta = \{1,\ldots,n\}$ pre $n \in \mathbb{N} - \{0\}$ je prípad Postovho korešpondenčného problému nad~abecedou~$\Sigma$ takou, že $\# \not\in \Sigma$.
Nech pre $i = 1,\ldots,n$ je $f(i) = x_i$ a $g(i) = y_i$.
Z prednášky je známe, že nasledujúce jazyky prislúchajúce k prípadu $(\Delta,f,g)$ sú bezkontextové:
\begin{align*}
L_X & = \{x_{i_1} \ldots x_{i_k} \# i_k \ldots i_i \mid k \in \mathbb{N} - \{0\};~i_1,\ldots,i_k \in \Delta\}, \\
L_Y & = \{y_{i_1} \ldots y_{i_k} \# i_k \ldots i_i \mid k \in \mathbb{N} - \{0\};~i_1,\ldots,i_k \in \Delta\}, \\
L_{XY} & = L_X \# L_Y^R.
\end{align*}
\endleftbar  
}

\begin{enumerate}
\item{Zostrojte bezkontextovú gramatiku generujúcu jazyk $L_{XY}^C$.
}
\item{Zistite, či existuje algoritmus, ktorý pre danú bezkontextovú gramatiku $G$ rozhodne, či $L(G)$ obsahuje aspoň jeden palindróm. 
}
\item{Zistite, či existuje algoritmus, ktorý pre danú bezkontextovú gramatiku $G$ rozhodne, či je jednoznačná.
}
\end{enumerate}

{\small
\leftbar
Nech $A = (K,\Sigma,\Gamma,\delta,q_0,F)$ je deterministický Turingov stroj taký, že $K \cap \Gamma = \emptyset$ a $\# \not\in K \cup \Gamma$. \emph{Jazykom platných výpočtov} stroja $A$ nazveme
jazyk $L_{PV}(A)$ pozostávajúci zo slov
\begin{displaymath}
w_0 \# w_1^R \# w_2 \# w_3^R \# \ldots w_k 
\end{displaymath} 
pre $k \in \mathbb{N}$ párne a
\begin{displaymath}
w_0 \# w_1^R \# w_2 \# w_3^R \# \ldots w_k^R 
\end{displaymath}
pre $k \in \mathbb{N}$ nepárne, pričom z obidvoch druhov patria do $L_{PV}(A)$ práve všetky slová spĺňajúce nasledujúce podmienky:
\begin{enumerate}[label=$(\roman*)$]
\item{Pre $i = 0,\ldots,k$ je $w_i$ konfigurácia stroja $A$ chápaná ako slovo $w \in K\mathbf{B}\Gamma^* \mathbf{B} \cup \mathbf{B}\Gamma^* K \Gamma^* \mathbf{B}$, v ktorom stav určuje pozíciu hlavy.  
}
\item{Konfigurácia $w_0$ je počiatočná.
}
\item{Konfigurácia $w_k$ je akceptačná.
}
\item{Pre $i = 1,\ldots,k$ je $w_{i - 1} \vdash_A w_i$.
} 
\end{enumerate}
\endleftbar  
}

\begin{enumerate}[resume]
\item{S použitím jazyka platných výpočtov dokážte nerozhodnuteľnosť problému prázdnosti prieniku dvoch bezkontextových jazykov.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že \emph{pravým kvocientom} jazyka $L$ nad abecedou $\Sigma$ podľa slova $x \in \Sigma^*$ nazývame jazyk
\begin{displaymath}
L / x = \{w \in \Sigma^* \mid wx \in L\}
\end{displaymath} 
a pre ľubovoľný jazyk $L' \subseteq \Sigma^*$ nazývame \emph{pravým kvocientom} jazyka $L$ podľa jazyka $L'$ jazyk
\begin{displaymath}
L / L' = \bigcup_{x \in L'} \left(L / x\right) = \{w \in \Sigma^* \mid \exists x \in L': wx \in L\}.
\end{displaymath}
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či existuje algoritmus, ktorý pre dvojicu bezkontextových gramatík $G_1,G_2$ rozhodne, či $L(G_1)/L(G_2) \in \mathscr{L}_{CF}$.
}
\item{Zistite, či existuje algoritmus, ktorý pre danú bezkontextovú gramatiku $G$ a deterministický konečný automat $A$ rozhodne,
či $L(G) \subseteq L(A)$. 
}
\item{Zistite, či existuje algoritmus, ktorý pre daný lineárne ohraničený automat $A$ rozhodne, či $L(A) \in \mathscr{L}_{CF}$.\goodbreak
}
\item{Uvažujme rozhodovací problém daný nasledovne:
\begin{description}
\item[Vstup:]{Kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$, o~ktorom je vopred známe, že $L(A) \in \mathscr{L}_{CF}$.  
}
\item[Výstup:]{\uv{Áno} práve vtedy, keď $L(A) = \emptyset$. 
}
\end{description}  
Zistite, či je uvedený problém rozhodnuteľný.\footnote{Zaujíma nás teda, či existuje rekurzívny jazyk $L$ taký, že jeho prienikom s jazykom všetkých kódov Turingových strojov akceptujúcich bezkontextové jazyky je jazyk kódov Turingových strojov akceptujúcich prázdny jazyk.} Svoje tvrdenie dokážte.
}
\end{enumerate}
\end{document}

