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

% vim: spell spelllang=cs

\assignment{12}
\exercise{1}
\points{0,5}
\duedate{13. 5. 2024 12:00}

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


\begin{document}

\begin{zadani}
    Mějme abecedu $\Sigma = \set{a, b, c}$.\\
    O~každém z~následujících tvrzení rozhodněte, zda je pravdivé pro všechny
    jazyky $L$, $R$, $M$ nad abecedou $\Sigma$, a svá tvrzení dokažte.
  
    \begin{enumerate}[a)]
      \item $L$ je CF, $M$ je DCF, $R$ je CS $\implies$ ($L$ $\cdot$ $M$) $\cap$ $R$ je CS
      \item $L$ $\cup$ $R$ není CF $\implies$ $L$ není DCF nebo $R$ není DCF
      \item $L$ je CF a $R$ je CF $\implies$ $L \setminus R$ je CF  
      
      \item $L$ má regulární podmnožinu, $\co{L}$ je RE $\implies$ $L$ je Rec
    \end{enumerate}
  
    \noindent
    Mohou se vám hodit známé jazyky a uzávěrové vlastnosti z~přednášky,~cvičení a ze skript.
    Pokud použijete tyto jazyky, nemusíte dokazovat jejich vlastnosti deklarované
    na přednášce/cvičení/ve skriptech, ale musíte se odkázat na místo, odkud je berete. 
    Podobně uzávěrové vlastnosti známé z přednášky/cvičení/skript
    nemusíte dokazovat. 
    Pokud naopak použijete jazyky, jejichž vlastnosti nebyly
    deklarovány na přednášce/cvičení, musíte tyto vlastnosti dokázat; tedy v případě příslušnosti jazyka do dané třídy sestrojit příslušnou gramatiku/TS/automat, a v případě nepříslušnosti dokázat např. pomocí PL. 
    Nemusíte dokazovat, že vaše gramatika/automat/TS generuje/rozpoznává chtěný jazyk.
    Všechny podpříklady by měly být řešitelné bez PL, ale klidně ho použijte, pokud vám pomůže.
    Pokud dokazujete, že tvrzení neplatí, udejte konkrétní protipříklad (tedy jazyky $L,\,R$ a $M$, t.ž. tvrzení pro ně neplatí).
  \end{zadani}


\begin{reseni}

\end{reseni}
\end{document}
