\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}
\newcommand{\fut}{\mathrm{fut}}

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

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

\begin{document}
\begin{center}
{\Large\textbf{Prémiová úloha č. 1}}
\end{center}
\thispageheading{\vspace{-42pt}\begin{flushright}\begin{tabular}{l} Formálne jazyky a automaty (1) \\ Letný semester 2023/24 \end{tabular}\end{flushright}}

Úlohu možno odovzdať \textbf{do stredy 20. marca 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
\emph{Nedeterministický konečný automat s množinou počiatočných stavov} je pätica $A = (K,\Sigma,\delta,I,F)$, kde $K$ je konečná množina stavov, $\Sigma$ je vstupná abeceda,
$\delta\colon K \times (\Sigma \cup \{\eps\}) \to 2^K$ je prechodová funkcia, $I \subseteq K$ je množina počiatočných stavov a $F \subseteq K$ je množina koncových stavov.

\emph{Konfiguráciou} takéhoto automatu $A$ nazveme ľubovoľnú dvojicu $(q,w)$ s $q \in K$ a $w \in \Sigma^*$, interpretovanú obvyklým spôsobom. \emph{Krok výpočtu} automatu $A$ je, rovnako ako pri bežných nedeterministických konečných automatoch,
binárna relácia $\vdash_A$ (alebo $\vdash$) na množine konfigurácií automatu $A$ taká, že pre $p,q \in K$ a~$u,v \in \Sigma^*$ je $(p,u) \vdash_A (q,v)$ práve vtedy, keď existuje $z \in \Sigma \cup \{\eps\}$ také,
že $u = zv$ a $q \in \delta(p,z)$. \emph{Jazyk akceptovaný automatom $A$} potom definujeme ako
\begin{displaymath}
L(A) = \{w \in \Sigma^* \mid \exists p \in I~\exists q \in F\colon (p,w) \vdash_A^* (q,\eps)\}.
\end{displaymath}
Všimnime si, že automat $A$ môže mať aj prázdnu množinu stavov -- v takom prípade je $L(A) = \emptyset$.

Stav $q \in K$ automatu $A = (K,\Sigma,\delta,I,F)$ nazveme \emph{dosiahnuteľným}, ak existujú $p \in I$ a $u \in \Sigma^*$ také, že
$(p,u) \vdash^* (q,\eps)$ a \emph{spätne dosiahnuteľným}, ak existuje $v \in \Sigma^*$ také, že pre nejaké $r \in F$ je $(q,v) \vdash^* (r,\eps)$.
Stav automatu $A$ nazveme \emph{užitočným}, ak~je súčasne dosiahnuteľný aj spätne dosiahnuteľný.

Automat $A$ nazveme \uv{bezepsilonovým}, ak pre všetky $q \in K$ je $\delta(q,\eps) = \emptyset$. \uv{Odepsilonovací} algoritmus zo zimného semestra možno ľahko upraviť
aj pre potreby automatov s množinou počiatočných stavov -- ku každému nedeterministickému konečnému automatu s množinou počiatočných stavov tak existuje ekvivalentný \uv{bezepsilonový} automat.\\

\emph{Deterministickým konečným automatom s čiastočnou prechodovou funkciou} nazveme \uv{bezepsilonový} nedeterministický konečný automat
$A = (K,\Sigma,\delta,I,F)$ s množinou počiatočných stavov taký, že $\lvert I\rvert \leq 1$ a~pre~všetky $q \in K$ a $c \in \Sigma$ je $\lvert\delta(q,c)\rvert \leq 1$.\\
(Terminológia tu vychádza z toho, že v netriviálnom prípade $\lvert I\rvert = 1$ by sme takéto automaty mohli ekvivalentne definovať ako \emph{deterministické} konečné automaty s prechodovou funkciou, ktorá pre niektoré vstupy môže mať aj nedefinované výstupy; takéto funkcie sa zvyknú nazývať \emph{čiastočnými}.)

\emph{Kodeterministickým konečným automatom} nazveme \uv{bezepsilonový} nedeterministický konečný automat $A = (K,\Sigma,\delta,I,F)$ s množinou počiatočných stavov taký, že $\lvert F\rvert \leq 1$ a pre každé dva rôzne stavy $p,q \in K$ a $c \in \Sigma$ je $\delta(p,c) \cap \delta(q,c) = \emptyset$;
automat $A$ teda má najviac jeden koncový stav a do každého stavu vedie na~každé písmeno najviac jeden prechod. Po obrátení všetkých prechodov a zámene úloh počiatočných a~koncových stavov
tak dostávame deterministický konečný automat s~čiastočnou prechodovou funkciou.\\

Ľahko možno dokázať, že každý regulárny jazyk $L$ je akceptovaný nejakým kodeterministickým konečným automatom obsahujúcim iba užitočné stavy (ak $L = \emptyset$, je tento automat prázdny).
\endleftbar  
}

\paragraph{Zadanie.} Nech $A = (K,\Sigma,\delta,I,F)$ je \uv{bezepsilonový} nedeterministický konečný automat s množinou počiatočných stavov. Ako $\mathrm{dfa}(A)$ označíme deterministický konečný automat (s~úplnou prechodovou funkciou) získaný z automatu $A$
aplikovaním podmnožinovej konštrukcie a následným obmedzením sa na dosiahnuteľnú časť výsledného automatu.

Najprv teda zostrojíme deterministický konečný automat $A' = (2^K,\Sigma,\delta',I,F')$, kde 
\begin{displaymath}
F' = \{Q \subseteq K \mid Q \cap F \neq \emptyset\}
\end{displaymath}
a pre všetky $Q \subseteq K$ a $c \in \Sigma$ je 
\begin{displaymath}
\delta'(Q,c) = \{p \in K \mid \exists q \in Q\colon p \in \delta(q,c)\}.
\end{displaymath}
Nech $D \subseteq 2^K$ je množina všetkých dosiahnuteľných stavov automatu $A'$ -- t.~j. 
\begin{displaymath}
D = \{Q \subseteq K \mid \exists w \in \Sigma^*\colon (I,w) \vdash_{A'}^* (Q,\eps)\}.
\end{displaymath}
Automat $\mathrm{dfa}(A)$ je potom daný ako $\mathrm{dfa}(A) = (D,\Sigma,\delta'',I,F'')$, kde $F'' = F' \cap D$ a~pre~všetky $Q \in D$ a $c \in \Sigma$ je $\delta''(q,c) = \delta'(q,c)$.
Ľahko vidieť, že $L(\mathrm{dfa}(A)) = L(A)$.
\bigskip

Dokážte, že pre ľubovoľný kodeterministický konečný automat $A$ obsahujúci iba spätne dosiahnuteľné stavy je $\mathrm{dfa}(A)$ minimálny deterministický konečný automat pre~jazyk~$L(A)$.
\end{document}