\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\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 6}
\bigskip
\hrule
\medskip

\begin{enumerate}
\item
Nech $\Sigma = \{a,b\}$. Uvažujme a-prekladače nad touto vstupnou
aj výstupnou abecedou. Ak $M$ je a-prekladač, nech $[M]$ označuje
nejaký jeho kód vo vhodnom kódovaní. Definujme jazyk

$$L_{2a-pr} = \{ \langle [M],[N] \rangle ~|~ M\text{ a }N \text{ sú a-prekladače};~(\exists w \in \Sigma^*)~ M(w) = N(w) \}.$$

Je jazyk $L_{2a-pr}$ rekurzívny? (Je to teda jazyk slov kódujúcich dvojice a-prekladačov, ktoré dávajú aspoň na jednom slove rovnaký výstup)

\item{
Definujme prestrihnutý PKP nasledovne. Inštanciou prestrihnutého PKP nazývame dvojicu $(X,Y)$ rovnakú ako pri štandardnom PKP. Riešením prestrihnutého PKP voláme neprázdne postupnosti indexov $(i_1, \ldots, i_k)$ a $(j_1, \ldots, j_l)$ také, že platí $x_{i_1} \ldots x_{i_k} = y_{j_1} \ldots y_{j_l}$. Rozhodnite a dokážte, či je pre danú inštanciu prestrihnutého PKP rozhodnuteľné povedať, či má riešenie.

{\em Poznámka k názvu:} Prestrihnutý PKP preto, že vytváranie riešenia si môžeme predstaviť tak, že vezmeme \uv{dominá} a vodorovne ich prestrihneme na polovicu. Potom sa snažíme z ich horných častí vyskladať rovnaký reťazec ako z ich dolných častí. Teda neukladáme za sebou celé dominá, ale zvlášť ukladáme ich vrchy a zvlášť spodky.
}

\item
Rozhodnite a dokážte, či je rozhodnuteľné pre daný deterministický LBA povedať, či akceptuje nekonečný jazyk. Súvisí táto otázka s 1. Riceho vetou? Ak áno, ako? Ak nie, prečo?

\item
Rozhodnite a dokážte, či je rozhodnuteľné o danom DTS $A$ povedať, či $A$ spraví pri výpočte na $acdc$ párny počet krokov? Súvisí táto otázka s 1. Riceho vetou? Ak áno, ako? Ak nie, prečo?

\item
Rozhodnite a dokážte, či je rozhodnuteľné o danom DTS $A$ povedať, či $A$ akceptuje aspoň jedno zo slov $010$ a $101$? Súvisí táto otázka s 1. Riceho vetou? Ak áno, ako? Ak nie, prečo?


\item
Je rozhodnuteľné, či pre daný NKA $A$ a číslo $k$ platí $|L(A)| = k$?
Je podobná otázka rozhodnuteľná pre PDA?

\end{enumerate}

\end{document}
