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

\pagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}
\setlist{topsep=0pt}

\begin{document}
\begin{center}
{\Large\textbf{Sada úloh na cvičenie č. 5}}
\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}[resume]
\item{Zostrojte kontextovú gramatiku generujúcu jazyk $L = \{a^i b^j c^i d^j \mid i,j \in \mathbb{N} - \{0\}\}$. Správnosť svojej konštrukcie zdôvodnite.
}
\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 je trieda $\mathscr{L}_{ECS}$ uzavretá na \uv{odmocninu}. Svoje tvrdenie dokážte.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že \emph{pravým kvocientom} jazyka $L$ nad abecedou $\Sigma$ podľa slova $x \in \Sigma^*$ nazývame jazyk
\begin{displaymath}
L / x = \{w \in \Sigma^* \mid wx \in L\}
\end{displaymath} 
a pre ľubovoľný jazyk $L' \subseteq \Sigma^*$ nazývame \emph{pravým kvocientom} jazyka $L$ podľa jazyka $L'$ jazyk
\begin{displaymath}
L / L' = \bigcup_{x \in L'} \left(L / x\right) = \{w \in \Sigma^* \mid \exists x \in L': wx \in L\}.
\end{displaymath}  
\endleftbar  
}

\begin{enumerate}[resume]
\item{Charakterizujte triedu všetkých jazykov $L/L'$ pre $L,L' \in \mathscr{L}_{ECS}$.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že \emph{prefixovým uzáverom} jazyka $L$ nad abecedou $\Sigma$ nazývame jazyk 
\begin{displaymath}
\mathrm{pref}(L) = \{u \in \Sigma^* \mid \exists v \in \Sigma^*: uv \in L\}.
\end{displaymath}
Hovoríme, že trieda jazykov $\mathscr{L}$ je \emph{prefixovo uzavretá}, ak pre všetky $L \in \mathscr{L}$ je aj $\mathrm{pref}(L) \in \mathscr{L}$.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či je trieda $\mathscr{L}_{ECS}$ prefixovo uzavretá. Svoje tvrdenie dokážte.
}
\end{enumerate}

{\small
\leftbar
Pripomeňme si, že \emph{komutatívnym uzáverom} jazyka $L$ nad abecedou $\Sigma$ nazývame jazyk 
\begin{displaymath}
[L] = \{u \in \Sigma^* \mid \exists v \in L~\forall c \in \Sigma: \#_c(u) = \#_c(v)\}.
\end{displaymath}
Jazyk $[L]$ tak obsahuje všetky slová $u$ nad abecedou $\Sigma$, z ktorých možno vhodným \uv{poprehadzovaním} písmen získať nejaké slovo $v$ z~jazyka~$L$.
Keby sme teda písmenám dovolili navzájom komutovať a slová líšiace sa iba poradím písmen by sme považovali za ekvivalentné, pozostával by jazyk $[L]$
z~práve všetkých slov ekvivalentných niektorému slovu z~$L$. Odtiaľ pomenovanie \uv{komutatívny uzáver}.

Hovoríme, že trieda jazykov $\mathscr{L}$ je \emph{komutatívne uzavretá}, ak pre všetky $L \in \mathscr{L}$ je aj $[L] \in \mathscr{L}$.  
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či je trieda $\mathscr{L}_{ECS}$ komutatívne uzavretá. Svoje tvrdenie dokážte.
}
\end{enumerate}

{\small
\leftbar
Nech $\Sigma$ je abeceda. Pripomeňme si, že \uv{\emph{shuffle}} dvojice slov $u,v \in \Sigma^*$ je definovaný nasledovne:
\begin{displaymath}
u \shuffle v = \{u_1 v_1 u_2 v_2 \ldots u_n v_n~|~ n \in \mathbb{N};~u_1,\ldots,u_n,v_1,\ldots,v_n \in \Sigma^*;~u = u_1 \ldots u_n;~v = v_1 \ldots v_n\}.
\end{displaymath}
Symbol $u \shuffle v$ teda označuje \emph{jazyk} všetkých možných \uv{premiešaní} slov $u$ a $v$ zachovávajúcich relatívne poradie symbolov v slovách $u,v$:
pre ľubovoľné faktorizácie $u = u_1 u_2 \ldots u_n$, 
$v = v_1 v_2 \ldots v_n$ slov $u$ a $v$, kde $u_1,\ldots,u_n$ a $v_1,\ldots,v_n$ sú \emph{slová}, patrí slovo $u_1 v_1 u_2 v_2 \ldots u_n v_n$ do jazyka $u \shuffle v$.
Niektoré z podslov $u_i$ resp.~$v_i$ pritom môžu byť aj prázdne. Napríklad teda
$aa \shuffle bb = \{aabb,abab,baab,abba,baba,bbaa\}$ a~$abc \shuffle d = \{abcd,abdc,adbc,dabc\}$.

Uvedenú operáciu na slovách možno prirodzeným spôsobom rozšíriť aj na \uv{shuffle} jazykov:
\begin{displaymath}
L_1 \shuffle L_2 = \bigcup_{\substack{u \in L_1\\ v \in L_2}} u \shuffle v,
\end{displaymath}   
čo možno ekvivalentne zapísať ako
\begin{displaymath}
L_1 \shuffle L_2 = \{u_1 v_1 u_2 v_2 \ldots u_n v_n~|~ n \in \mathbb{N};~u_1,\ldots,u_n,v_1,\ldots,v_n \in \Sigma^*;~u_1 \ldots u_n \in L_1;~v_1 \ldots v_n \in L_2\}.
\end{displaymath}
Do jazyka $L_1 \shuffle L_2$ teda patria všetky možné \uv{premiešania} slov $u$ a $v$, kde $u \in L_1$ a $v \in L_2$.
\endleftbar  
}

\begin{enumerate}[resume]
\item{Zistite, či je trieda $\mathscr{L}_{ECS}$ uzavretá na operáciu \uv{shuffle}. Svoje tvrdenie dokážte. 
}
\item{Označme ako $\mathscr{L}_{detECS}$ triedu jazykov akceptovaných \emph{deterministickými} lineárne ohraničenými automatmi. Zistite, či je trieda $\mathscr{L}_{detECS}$ uzavretá na komplement.
Svoje tvrdenie dokážte.
}
\item{Formálne zadefinujte (nedeterministické) lineárne ohraničené automaty s dvoma hlavami a preskúmajte ich výpočtovú silu.
}
\end{enumerate}

\end{document}

