\documentclass[a4paper]{article}
\usepackage[slovak]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage[small,bf]{caption}
\usepackage{subcaption}
\usepackage{xcolor}

\def\eps{\varepsilon}
\def\Lecs{\mathscr{L}_{\it ECS}}
\def\Lrec{\mathscr{L}_{\it rec}}
\def\Lre{\mathscr{L}_{\it RE}}
\def\Lcf{\mathscr{L}_{\it CF}}
\def\R{{\cal R}}
\def\N{\mathbb{N}}

\pagestyle{empty}
\setlength{\parindent}{0pt}

\newenvironment{modenumerate}
  {\enumerate\setupmodenumerate}
  {\endenumerate}

\newif\ifmoditem
\newcommand{\setupmodenumerate}{%
  \global\moditemfalse
  \let\origmakelabel\makelabel
  \def\moditem##1{\global\moditemtrue\def\mesymbol{##1}\item}%
  \def\makelabel##1{%
    \origmakelabel{##1\ifmoditem\rlap{\mesymbol}\fi\enspace}%
    \global\moditemfalse}%
}

\begin{document}
\begin{center}
{\Large\textbf{Tretia sada bodovaných domácich úloh}}
\end{center}

Úlohy tejto sady je potrebné odovzdať \textbf{do pondelka, 17.4., 12:03} do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).


\begin{enumerate}


\item
\begin{enumerate}[label=\alph*)]
\item 
Uvažujme tabuľku rozhodnuteľnosti otázok o triedach Chomského hierarchie, ktorá sa vyskytla na prednáške a ktorú môžete nájsť v skriptách na strane 86. Doplňte do tejto tabuľky nasledovný riadok a vaše odpovede odôvodnite: 

\begin{center}
Pre dané $G_1, G_2, G_3$ zistiť, či $ (L(G_1) \cup L(G_2))^R = L(G_3)^2 $.
\end{center}

\item
Je pre dané LBA $A$, slovo $w$ a symbol $c$ rozhodnuteľné, či $A$ dokáže akceptovať $w$ bez toho, aby niekedy počas výpočtu zapísalo na pásku $c$?
\end{enumerate}



\item
Nasledujúce úlohy vyriešte pomocou Riceových viet. Za iné riešenia je automaticky 0 bodov.
\begin{enumerate}[label=\alph*)]
\item 
Uvažujme nasledovný jazyk kódov deterministických Turingových strojov: 
\begin{displaymath}
L = \{ \langle A \rangle ~|~ L(A) \subseteq L_{\it HALT} \}
\end{displaymath} 
Platí $ L \in \Lrec $? Ak nie, platí aspoň $ L \in \Lre$?

\item 
Uvažujme nasledovný jazyk kódov deterministických Turingových strojov: 
\begin{displaymath}
L = \{ \langle A \rangle ~|~ L_{\it HALT} \subseteq L(A) \subseteq L_{\it U} \}
\end{displaymath} 
Platí $ L \in \Lrec $? Ak nie, platí aspoň $ L \in \Lre$?
\end{enumerate}

\end{enumerate}

Každú úlohu odovzdajte na \textbf{osobitný papier}. Dbajte o čitateľnosť vašich riešení. Odovzdané riešenia budú hodnotené aj po formálnej stránke. V prípade, že sa budete odvolávať na Riceove vety a budete tvrdiť, že nejaká podmienka z nich platí resp. neplatí, treba toto tvrdenie poriadne dokázať. Nestačí iba konštatovanie \uv{platí} resp. \uv{neplatí}.

\end{document}

