\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}

\newcommand{\eps}{\varepsilon}

\geometry{
  a4paper,
  top=25mm,
  bottom=18mm,
  right=21mm,
  left=22mm
}

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

Úlohy tejto sady je potrebné odovzdať \textbf{do stredy 24. apríla 2024, 13:00} do krabice,
ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254), prípadne osobne na cvičeniach.

{\small
\leftbar
Bezkontextová gramatika $G = (N,T,P,\sigma)$ je \emph{lineárna}, ak $P \subseteq N \times (T^*NT^* \cup T^*)$.
Jazyk $L$ je \emph{lineárny}, ak~existuje lineárna gramatika $G$ taká, že $L(G) = L$.
\bigskip

Nech $\Sigma$ je abeceda a $L \subseteq \Sigma^*$ jazyk. Jazyk 
\begin{displaymath}
\mathrm{MIN}(L) = \{w \in L \mid \forall u,v \in \Sigma^*\colon (w = uv ~\land~ u \in L) \Rightarrow v = \eps\}
\end{displaymath} 
potom pozostáva zo všetkých slov $w$ z jazyka $L$ takých, že žiaden z ich \emph{vlastných} prefixov nepatrí do~jazyka~$L$.
Podobne
\begin{displaymath}
\mathrm{MAX}(L) = \{w \in L \mid \forall x \in \Sigma^+\colon wx \not\in L\}
\end{displaymath} 
pozostáva zo všetkých slov $w$ z jazyka $L$, ktoré nie sú \emph{vlastným} prefixom žiadneho iného slova z jazyka $L$.
\endleftbar  
}

\begin{enumerate}
\item{Zistite, či sú nasledujúce problémy rozhodnuteľné:
\begin{enumerate}[label=\alph*)]
\item{Pre bezkontextovú gramatiku $G$ a pre deterministický konečný automat $A$ rozhodnúť, či~$L(G) \cap L(A) = \emptyset$.
}
\item{Pre dvojicu lineárnych gramatík $G_1,G_2$ rozhodnúť, či $L(G_1) \cap L(G_2) = \emptyset$.
}
\item{Pre bezkontextovú gramatiku $G$ rozhodnúť, či existuje slovo $w$ také, že $w^2 \in L(G)$.
}
\item{Pre bezkontextovú gramatiku $G$ rozhodnúť, či $L(G)$ obsahuje nekonečne veľa palindrómov.
}
\item{Pre bezkontextovú gramatiku $G$ rozhodnúť, či $L(G)$ obsahuje aspoň jedno slovo nepárnej dĺžky.
}
\item{Pre deterministický konečný automat $A$ rozhodnúť, či $\mathrm{MIN}(L(A)) \in \mathscr{R}$.
}
\item{Pre bezkontextovú gramatiku $G$ rozhodnúť, či $\mathrm{MIN}(L(G)) \in \mathscr{L}_{CF}$.
}
\item{Pre bezkontextovú gramatiku $G$ rozhodnúť, či $\mathrm{MAX}(L(G)) \in \mathscr{L}_{CF}$.
}
\item{Pre lineárne ohraničený automat $A$ nad vstupnou abecedou $\Sigma$ a pre~homomorfizmus $h\colon \Sigma^* \to \Gamma^*$ daný obrazmi jednotlivých písmen rozhodnúť,
či $h(L(A)) \in \mathscr{L}_{ECS}$.
}
\end{enumerate}
Svoje tvrdenia dokážte.
}
\end{enumerate}
\end{document}

