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

{\small
\leftbar
\emph{Prípadom} alebo \emph{inštanciou} Postovho korešpondenčného problému (PKP) nad abecedou $\Sigma$ nazývame trojicu $(\Delta,f,g)$, kde $\Delta = \{1,\ldots,n\}$ s $n \in \mathbb{N} - \{0\}$ je abeceda
a $f,g\colon \Delta^* \to \Sigma^*$ sú nevymazávajúce homomorfizmy. To zodpovedá sade $n$ dlaždíc
\begin{center}
\domino{$f(1)$}{$g(1)$} \domino{$f(2)$}{$g(2)$} \ldots \domino{$f(n)$}{$g(n)$}\,. 
\end{center}
\emph{Riešením} prípadu PKP $(\Delta,f,g)$ nazývame slovo $x \in \Delta^+$ také, že $f(x) = g(x)$.

Prípadom modifikovaného Postovho korešpondenčného problému (MPKP) rozumieme trojicu $(\Delta,f,g)$ definovanú rovnakým spôsobom ako pri PKP.
Od riešenia ale navyše požadujeme, aby začínalo prvou dlaždicou -- rozumieme ním teda slovo $x \in 1\Delta^*$ také, že $f(x) = g(x)$.
\endleftbar  
}

\begin{enumerate}
\item{Uvažujme prípad PKP pozostávajúci z nasledujúcej sady dlaždíc:
\begin{center}
\domino{$aab$}{$ab$} \domino{$ab$}{$ba$} \domino{$acb$}{$b$} \domino{$bb$}{$aaa$} \domino{$aaa$}{$aa$}\,.
\end{center}
\begin{enumerate}[label=\alph*)]
\item{Zapíšte tento prípad formálne ako trojicu $(\Delta,f,g)$.
}
\item{Zistite, či má daný prípad PKP riešenie. Ak áno, uveďte aspoň jedno. Ak nie, dokážte.
}
\end{enumerate}
}
\item{Uvažujme prípad MPKP pozostávajúci z nasledujúcej sady dlaždíc:
\begin{center}
\domino{$aab$}{$a$} \domino{$aa$}{$a$} \domino{$bba$}{$aa$} \domino{$a$}{$ab$} \domino{$a$}{$aaaa$}\,. 
\end{center}
\begin{enumerate}[label=\alph*)]
\item{Zapíšte tento prípad formálne ako trojicu $(\Delta,f,g)$.
}
\item{Štandardnou konštrukciou zostrojte prípad PKP, ktorý má riešenie práve vtedy, keď má riešenie uvedený prípad MPKP.
}
\item{Nájdite riešenie uvedeného prípadu MPKP a k nemu prislúchajúce riešenie ekvivalentného prípadu PKP. 
}
\end{enumerate}
}
\item{Preverte rozhodnuteľnosť PKP nad unárnou abecedou $\Sigma = \{a\}$.
}
\end{enumerate}

{\small
\leftbar
Hovoríme, že rozhodovacie problémy $P,R \subseteq \Sigma^*$ sú \emph{rovnako ťažké} (vzhľadom na turingovskú redukciu) alebo \emph{turingovsky ekvivalentné},
ak súčasne $P \leq_T R$ a $R \leq_T P$. 
\endleftbar  
}

\begin{enumerate}[resume]
\item{Uvažujme rozhodovací problém, kde na vstupe je prípad PKP s jednou označenou dlaždicou 
a treba rozhodnúť, či existuje jeho riešenie obsahujúce aspoň jeden výskyt označenej dlaždice. Zistite, či je tento problém (vzhľadom na turingovskú redukciu) rovnako ťažký ako PKP.
Svoje tvrdenie dokážte. 
}
\item{Uvažujme rozhodovací problém, kde na vstupe je prípad PKP s jednou označenou dlaždicou 
a treba rozhodnúť, či existuje jeho riešenie obsahujúce práve dva výskyty označenej dlaždice. Zistite, či je tento problém (vzhľadom na turingovskú redukciu) rovnako ťažký ako PKP.
Svoje tvrdenie dokážte.
}
\item{Uvažujme rozhodovací problém, kde na vstupe je prípad PKP, v ktorom je každá dlaždica ofarbená bielou alebo čiernou farbou a treba rozhodnúť, či existuje jeho riešenie
obsahujúce z každej farby aspoň jednu dlaždicu. Zistite, či je tento problém (vzhľadom na turingovskú redukciu) rovnako ťažký ako PKP. Svoje tvrdenie dokážte.
}
\item{Uvažujme rozhodovací problém, kde na vstupe je prípad PKP, v ktorom je každá dlaždica ofarbená bielou alebo čiernou farbou a dve prirodzené čísla $m,n$;
treba rozhodnúť, či existuje riešenie daného prípadu PKP obsahujúce presne $m$ bielych a presne $n$ čiernych dlaždíc.
Zistite, či je tento problém (vzhľadom na turingovskú redukciu) rovnako ťažký ako PKP. Svoje tvrdenie dokážte.
}
\item{Uvažujme rozhodovací problém, kde na vstupe je prípad PKP, v ktorom je každá dlaždica ofarbená bielou alebo čiernou farbou a treba rozhodnúť, či existuje jeho riešenie
obsahujúce nepárny počet bielych dlaždíc. Zistite, či je tento problém (vzhľadom na turingovskú redukciu) rovnako ťažký ako PKP. Svoje tvrdenie dokážte.
}
\item{Zistite, či existuje algoritmus, ktorý pre danú dvojicu a-prekladačov $M_1,M_2$ so vstupnou abecedou $\Sigma$
rozhodne, či existuje slovo $w \in \Sigma^*$ také, že $M_1(w) = M_2(w)$. 
}
\item{Zistite, či existuje algoritmus rozhodujúci ekvivalenciu dvojice a-prekladačov s rovnakými vstupnými abecedami -- pre dané dva a-prekladače $M_1,M_2$ so vstupnou abecedou $\Sigma$ 
je teda potrebné rozhodnúť, či pre všetky $L \subseteq \Sigma^*$ je $M_1(L) = M_2(L)$. 
}
\end{enumerate}

\end{document}

