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


\begin{enumerate}


\item
Uvažujme nasledovný rozhodovací problém:
\begin{itemize}
\item {\bf VSTUP:} $\kodTS{A}$ - kód DTS; $\kodTS{B}$ - kód LBA
\item {\bf VÝSTUP:} Áno {\bf práve vtedy keď} existujú aspoň
tri slová také, že $B$ ich akceptuje a $A$ ich neakceptuje.
\end{itemize}

Je tento problém rozhodnuteľný? Ak nie, je čiastočne rozhodnuteľný?

Súvisí táto otázka s Riceovými vetami? Ak áno, ako? Ak nie, prečo?

\item
Uvažujme nasledovné rozhodovacie problémy. O každom dokážte či je rozhodnuteľný alebo aspoň čiastočne rozhodnuteľný. Ak sa to dá dokázať pomocou Riceových viet, spravte to tak. Ak nie, zdôvodnite, prečo sa to nedá pomocou nich a dokážte to inak.
\begin{enumerate}[label=\alph*)]
\item Rozhodnúť, či daný DTS akceptuje doplnok nejakého konečného jazyka (ako univerzum, vzhľadom na ktoré sa robí doplnok uvažujeme vstupnú abecedu stroja na vstupe).
\item Rozhodnúť o danom DTS $A$ či existuje slovo $w$ také, že $A$ pri výpočte na $w$ použije stav číslo $7$.
\item Rozhodnúť či daný DTS akceptuje kód aspoň jednej inštancie PKP,  ktorá nemá riešenie.
\end{enumerate}



\item
Uvažujme problémy:
\begin{enumerate}[label=\alph*)]
	\item Rozhodnúť,  o danom DTS $A$, či platí $|L(A)| = |L(A)^*|$.
	\item Rozhodnúť o danom DTS $A$,  či platí $L(A) \subsetneq L(A)^*$.
	\item Rozhodnúť o danom DTS $A$, či platí $L(A) - L_{Halt} \neq \emptyset$.
\end{enumerate}

Ku každému z nich uveďte všetky podmienky druhej Riceovej vety, ktoré preň nie sú splnené a zdôvodnite, prečo nie sú splnené.

\item
Uvažujme problémy:

\begin{enumerate}[label=\alph*)]
	\item Rozhodnúť o danom DTS, či akceptuje aspoň 11 slov
	obsahujúcich podslovo $ababb$.
	\item Rozhodnúť o danom DTS, či akceptuje kód nejakého DTS $B$ takého,
	že $L(B) \in \Lecs$.
	\item Rozhodnúť  o danom DTS, či akceptuje menej ako 25 slov dĺžky väčšej ako $31$.
\end{enumerate}

Odvolávajúc sa na Riceove vety, pre každý z problémov rozhodnite a dokážte, či je rekurzívny a či je rekurzívne vyčísliteľný.

\item
Nech $ \Pi $ je preklad daný jednoduchou prekladovou schémou a nech  $ pr_1(\Pi), pr_2(\Pi) $ sú jazyky slov z prvých resp. druhých komponent dvojíc prekladu. Rozhodnite či platí a dokážte: $ pr_1(\Pi) \in \R \iff pr_2(\Pi) \in \R $.

\item Nech $ \Sigma $ je ľubovoľná abeceda. Nech $ h : \Sigma^* \rightarrow \Sigma^* $ je homomorfizmus. Nech $ \Phi \subseteq \Sigma^* \times \Sigma^* $ je preklad definovaný nasledovne $ \Phi = \{ (u,h(u)) ~|~ u \in \Sigma^* \} $. Skonštruujte jednoduchú prekladovú scému $ \Sigma $ takú, že platí $ L(\Pi) = \Phi $. Formálne dokážte správnosť vašej konštrukcie.


\end{enumerate}

\end{document}
