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

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

\begin{document}

\centerline{\Large\sc Sada úloh na cvičenie 5}
\bigskip
\hrule
\medskip
\centerline{\bf Definície:}

Nech $ (X,Y) $ kde $ X=(x_1, \ldots, x_n) $ a $ Y=(y_1, \ldots, y_n) $ je inštancia PKP nad abecedou $\Sigma$. Definujeme nasledovné jazyky:

\begin{itemize}
\item $L_{X} = \{ x_{i_1} x_{i_2} \ldots x_{i_k} \# i_k \ldots i_2 i_1  ~|~ k \in \N^+ ;~ i_j \in \{1,\ldots, n\} \text{ pre } 1 \leq j \leq k \}$

\item $L_{Y} = \{ y_{i_1} y_{i_2} \ldots y_{i_k} \# i_k \ldots i_2 i_1  ~|~ k \in \N^+ ;~ i_j \in \{1,\ldots, n\} \text{ pre } 1 \leq j \leq k \} $

\item $L_{XY} = L_{X}\cdot\{\#\}\cdot L_{Y}^R$.

\item
$ L_{sym} = \{ w \in (\Sigma \cup \{\#,1,2,\ldots,n \})^* ~|~ w = w^R \} $

\end{itemize}

\medskip
\hrule
\bigskip



\begin{enumerate}

\item
Štandardnou konštrukciou z prednášky zostrojte inštanciu PKP, ktorá má riešenie práve vtedy, keď má riešenie nasledujúca inštancia MPKP.

\domino{bbb}{b}
\domino{ba}{baa}
\domino{aa}{b}
\domino{b}{abb}


\item
Je daný deterministický Turingov stroj $A = (\{q_0, q_1, q_2, q_F\}, \{a,b\}, \{a,b,B'\},  \delta,
q_0, \{q_F\})$, kde
\begin{eqnarray*}
\delta(q_0, B) &=& (q_F, B', 0) 
\\
\delta(q_0, a) &=& (q_1, a, 1)  
\\
\delta(q_1, a) &=& (q_1, a, 1)
\\
\delta(q_1, b) &=& (q_2, b, 0)
\\
\delta(q_1, B) &=& (q_F, B', - 1)
\end{eqnarray*}

Zostrojte prípad MPKP, ktorý má riešenie práve vtedy, ak $A$ akceptuje slovo $abaa$. Použite vhodnú modifikáciu konštrucie z prednášky, ktorá zostrojovala k danému DTS a danému vstupnému slovu inštanciu MPKP majúcu riešenie práve vtedy keď daný DTS na danom vstupe zastaví. {\it Poznámka:} Nezaoberajte sa tým, čo tento Turingov stroj počíta a či to je vôbec \uv{zmysluplné.} Cieľom úlohy je správne spraviť požadovanú konštrukciu inštancie MPKP.


\item
Definujme upravený PKP, ktorý funguje podobne ako PKP, ale zaujíma nás,  či existuje riešenie, v ktorom je prvé domino použité aspoň raz (nie nutne na začiatku).

Nájdite algoritmus, ktorý inštanciu upraveného PKP (danú na vstupe) prerobí na ekvivalentnú inštanciu štandardného PKP. Ekvivalentnou inštanciou štandardného PKP sa rozumie taká inštancia štandardného PKP, ktorá má riešenie práve vtedy, keď má riešenie inštancia upraveného PKP zo vstupu.

Zdôvodnite správnosť vášho algoritmu.

\item Rozhodnite, či PKP je rozhodnutelný nad unárnou abecedou. Vaše tvrdenie poriadne zdôvodnite.

\item
Majme danú ľubovoľnú inštanciu PKP, k nej máme definované jazyky v zmysle poznámky pod nadpisom.
\begin{enumerate}[label=\alph*)]
\item Dokážte, že jazyk $L_{XY}\cap L_{sym}$ je buď prázdny, alebo nekonečný.
\item Pomocou  PDA dokážte, že jazyk $L_{X}^C$  je bezkontextový.
\end{enumerate}

\item
Majme danú ľubovoľnú inštanciu PKP, k nej máme definované jazyky v zmysle poznámky pod nadpisom. Pomocou konštrukcie gramatík dokážte, že jazyky $L_{XY}^C$ a $L_{sym}^C$ sú bezkontextové.


\end{enumerate}

\end{document}
