\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\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{Druhá sada bodovaných domácich úloh}}
\end{center}

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

\begin{enumerate}
\item{
Definujeme operáciu {\bf $\varphi$} na jazykoch nasledovne:

\begin{displaymath}
\varphi(L_1,L_2) = \{ v \in L_1L_2 ~|~ (\exists u \in L_2^C)~ |u| = \left\lfloor \dfrac{|v|}{2} \right\rfloor \}.
\end{displaymath}

Formálne dokážte, že trieda $\Lecs$ je uzavretá na túto operáciu. Konštrukcie vo vašom dôkaze treba spraviť poriadne formálne, ich správnosť stačí slušne slovne zdôvodniť. Myslite na to, že slovné zdôvodnenie by malo čitateľovi rozumne vysvetliť ako vaše LBA alebo ECSG funguje a malo by mu značne uľahčiť čítanie formálnej definície. Vopred odporúčame si riešenie najprv dva krát premyslieť a potom začať písať, aby ste sa príliš neupísali.
}

\item{
Definujeme farebný PKP nad abecedou $\Sigma$ nasledovne. Štvoricu $(X,Y,B,R)$ takú, že platí:
\begin{enumerate}
\item $X = (x_1, \ldots, x_n)$ kde pre $1 \leq i \leq n$ platí $x_i \in \Sigma^+$.
\item $Y = (y_1, \ldots, y_n)$ kde pre $1 \leq i \leq n$ platí $y_i \in \Sigma^+$.
\item $B,R \subseteq \{1, \ldots, n \}$, $B \cup R = \{1, \ldots, n \}$, $B \cap R = \emptyset$.
\end{enumerate}
budeme nazývať inštanciou farebného PKP. Táto inštancia má riešenie ak existujú $i_1, \ldots, i_k \in R$ a $j_1, \ldots, j_l \in B$, kde $k,l \in \N$ a navyše $k+l>0$, také, že platí $x_{i_1} \ldots x_{i_k}x_{j_1}\ldots x_{j_l} = y_{i_1} \ldots y_{i_k}y_{j_1}\ldots y_{j_l}$.

Neformálne povedané, definujeme variáciu PKP takú, že každé domino ofarbíme alebo na modro alebo na červeno. Pýtame sa, či existuje riešenie také, že v ňom sú najprv dominá červenej farby a následne dominá modrej farby. Teda riešenie musí byť tvorené najprv červeným úsekom a potom modrým úsekom. Upozorňujeme, že naša definícia povoluje zafarbiť všetky dominá iba jednou farbou a rovnako povoluje, aby jeden z úsekov v riešení bol prázdny. Teda aj riešenia používajúce iba modré (resp. iba červené) dominá sú prípustnými riešeniami.

Dokážte, že takto definovaný farebný PKP je rozhodnuteľný práve vtedy, keď je rozhodnuteľný štandardný PKP.
}
\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.


\end{document}

