\documentclass{fja}
\usepackage[shorthands=off,czech]{babel}

% vim: spell spelllang=cs
% gen: ready

\assignment{12}
\exercise{2}
\points{0,5}
\duedate{16. 5. 2022 12:00}

%%% ZDE NAPISTE SVOJE UCO A JMENO
\name{}
\uco{}


\begin{document}
\begin{zadani}
Mějme zadanou abecedu $\Sigma = \set{a, b, c}$ a jazyk $L = \set{w\#p\mid w\in\Sigma^*, p \text{ je permutace } w}$.

\medskip
\noindent
Příklady slov, která patří do jazyka $L$: $\#$, $aa\#aa$, $abc\#abc$, $abc\#cab$, $abcccaaba\#cacacbaba$.\\
Příklady slov, která nepatří do jazyka $L$: $\varepsilon$, $abab$, $abcac\#acac$, $aaa\#aaaa$, $bbb\#b$, $abcac\#cabab$.

\medskip
\noindent
Úlohu můžete řešit jedním z následujících formalismů. Nekonstruujte LBA a zároveň gramatiku, stačí si vybrat \textbf{jeden} ze způsobů a úlohu řešit pomocí něj.
\begin{itemize}
\item Sestrojte deterministický lineárně ohraničený automat (LBA) akceptující jazyk $L$.\\
Nejdříve slovně popište fungování LBA včetně popisu funkcionality jednotlivých stavů, poté ho zadefinujte i formálně. Váš LBA může mít nanejvýš \textbf{18} stavů (včetně stavů accept a reject).

\item Sestrojte kontextovou gramatiku (CSG) generujíci jazyk $L$.\\
Nejdříve slovně popište hlavní myšlenku fungování vaší gramatiky, včetně popisu funkcionality jednotlivých pravidel, poté ji zadefinujte i formálně. Vaše gramatika může mít nanejvýš \textbf{20} pravidel.
\end{itemize}
\medskip\noindent
\textit{Poznámka: Pokud píšete řešení v \TeX u a nevejde se vám, před odevzdáním prosím odmažte zadání. }
\end{zadani}

\begin{reseni}

%%% SEM PISTE SVE RESENI

\end{reseni}
\end{document}
