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

\begin{enumerate}
\item{Zistite, či sú nasledujúce problémy rozhodnuteľné alebo aspoň rekurzívne vyčísliteľné:
\begin{enumerate}[label=\alph*)]
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A) = h(L)$ pre nejaký jazyk $L \in \mathscr{L}_{CF}$ a homomorfizmus $h$. 
}
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A) = h(L)$ pre nejaký jazyk $L \in \mathscr{L}_{ECS}$ a homomorfizmus $h$. 
}
\end{enumerate}
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že pre ľubovoľnú abecedu $\Sigma$ a jazyk $L \subseteq \Sigma^*$ je $\sqrt{L} = \{w \in \Sigma^* \mid ww \in L\}$.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či sú nasledujúce problémy rozhodnuteľné alebo aspoň rekurzívne vyčísliteľné:
\begin{enumerate}[label=\alph*)]
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $\sqrt{L(A)} \in \mathscr{L}_{RE}$. 
}
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A) = \sqrt{L(A)}$. 
}
\end{enumerate}
}
\item{Zistite, pre ktoré $k \in \mathbb{N}$ sú nasledujúce problémy rozhodnuteľné a pre ktoré $k \in \mathbb{N}$ sú rekurzívne vyčísliteľné:
\begin{enumerate}[label=\alph*)]
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A)$ obsahuje aspoň jedno slovo dĺžky ostro menšej, než $k$. 
}
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $A$ urobí na nejakom vstupnom slove aspoň $k$ krokov. 
}
\end{enumerate}
}
\item{Zistite, pre ktoré $n \in \mathbb{N}$ a $q \in \mathbb{N} - \{0\}$ sú nasledujúce problémy rozhodnuteľné resp. rekurzívne vyčísliteľné:
\begin{enumerate}[label=\alph*)]
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A)$ obsahuje práve $n$ slov dĺžky deliteľnej $q$. 
}
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A)$ obsahuje aspoň $n$ slov dĺžky deliteľnej $q$. 
}
\end{enumerate}
}
\end{enumerate}

{\small
\leftbar
Nech $\Sigma$ je ľubovoľná abeceda, na ktorej je definované úplné usporiadanie $\leq$. Pri \emph{koreňovom usporiadaní} $\preceq$ na $\Sigma^*$ sú slová usporiadané najprv podľa
svojej dĺžky a slová rovnakej dĺžky sú usporiadané lexikograficky. Pre $u,v \in \Sigma^*$ je teda $u \preceq v$ práve vtedy, keď $\lvert u\rvert < \lvert v\rvert$,
alebo keď $\lvert u\rvert = \lvert v\rvert =: n$ a súčasne buď $u = v$, alebo existujú písmená $a_1,\ldots,a_n,b_1,\ldots,b_n \in \Sigma$ také, že $u = a_1 \ldots a_n$, $v = b_1 \ldots b_n$
a pre nejaké $k \in [n]$ je $a_k < b_k$ a $a_j = b_j$ pre $j = 1,\ldots,k-1$.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či sú nasledujúce problémy rozhodnuteľné alebo aspoň rekurzívne vyčísliteľné:
\begin{enumerate}[label=\alph*)]
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A)$ obsahuje aspoň jedno slovo dĺžky $n \in \mathbb{N}$ takej, že $n$-tý kód stroja $\langle B\rangle$ v~koreňovom usporiadaní na $\{0,1\}^*$ patrí do diagonálneho jazyka $L_D$. 
}
\item{Pre kód $\langle A\rangle$ deterministického Turingovho stroja $A$ nad vstupnou abecedou $\Sigma = \{0,1\}$ zistiť,
či $L(A)$ obsahuje aspoň jedno slovo dĺžky $n \in \mathbb{N}$ takej, že $n$-tý kód stroja $\langle B\rangle$ v~koreňovom usporiadaní na $\{0,1\}^*$ nepatrí do diagonálneho jazyka $L_D$.
} 
\end{enumerate}
}
\item{Nájdite príklad vlastnosti $\mathscr{S}$ rekurzívne vyčísliteľných jazykov, ktorá nespĺňa žiadnu z troch podmienok druhej Riceovej vety. 
}
\item{Zistite, či platí obdoba prvej Riceovej vety pre vlastnosti \emph{rekurzívnych} jazykov: musí byť každá netriviálna vlastnosť rekurzívnych jazykov nerozhodnuteľná?
Ako reprezentáciu rekurzívnych jazykov uvažujte kódy deterministických Turingových strojov, u ktorých je \emph{a priori} garantované zastavenie na každom vstupe.
}
\item{Sformalizujte pojem \emph{vlastnosti dvojice rekurzívne vyčísliteľných jazykov} (príkladmi by mali byť napríklad rovnosť, neprázdnosť prieniku, atď.) a jej rozhodnuteľnosti.
Sformulujte a dokážte obdobu prvej Riceovej vety pre vlastnosti dvojíc rekurzívne vyčísliteľných jazykov a aplikujte ju na dôkaz nerozhodnuteľnosti aspoň jednej takejto vlastnosti.
}
\end{enumerate}

\end{document}

