\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\usepackage{graphicx}
\usepackage{pifont}

\pagestyle{empty}

\topmargin -3mm
\headsep 0mm
\headheight 3mm
\textheight 235mm
\textwidth 165mm
\oddsidemargin 0mm
\evensidemargin 0mm
\footskip 10mm

\newcommand{\eps}{\varepsilon}
\newcommand{\coL}{co\mbox{$-$}L}
\newcommand{\move}{\rightarrow}

\newcommand{\zadani}[2]{
{\large
\noindent {\bf IB102 -- úkol #1 \hfill Odevzdání: #2\\[-4mm]}
\noindent\hrule
\vspace{2mm}
\noindent Vypracoval(a):\hspace{7cm}UČO:\\
\noindent Skupina:
\vspace{2mm}
\hrule
\bigskip}
}

\newcommand{\reseni}[2]{
{\large
\noindent {\bf  IB102 -- úkol #1 -- řešení \hfill Odevzdání: #2\\[-4mm]}
\noindent\hrule
\vspace{2mm}
\noindent Vypracoval: James Bond \hspace{4.2cm}UČO: 007\ \ \\
\noindent Skupina: MI6
\vspace{2mm}
\hrule
\bigskip}
}


% neterminaly
\newcommand{\NTfont}{\textsf}
\newcommand{\Veta}{V}
\newcommand{\VVeta}{W}
\newcommand{\Podmet}{\NTfont{Podmět}}
\newcommand{\Predmet}{\NTfont{Předmět}}
\newcommand{\Sloveso}{\NTfont{Sloveso}}
\newcommand{\Kdo}{\NTfont{Kdo}}
\newcommand{\Koho}{\NTfont{Koho}}
\newcommand{\Jakou}{\NTfont{Jakou}}

% terminaly
\newcommand{\Tfont}[1]{\textbf{\underline{#1}}}
\newcommand{\carka}{\Tfont{,}}
\newcommand{\ktera}{\Tfont{která}}
\newcommand{\zena}{\Tfont{žena}}
\newcommand{\ruze}{\Tfont{růže}}
\newcommand{\pisen}{\Tfont{píseň}}
\newcommand{\kost}{\Tfont{kost}}
\newcommand{\zenu}{\Tfont{ženu}}
\newcommand{\ruzi}{\Tfont{růži}}
\newcommand{\krasnou}{\Tfont{krásnou}}
\newcommand{\tvrdou}{\Tfont{tvrdou}}
\newcommand{\ostrou}{\Tfont{ostrou}}
\newcommand{\zpiva}{\Tfont{zpívá}}
\newcommand{\vidi}{\Tfont{vidí}}
\newcommand{\vari}{\Tfont{vaří}}


\begin{document}

\newcommand{\ol}{\mathord{<}}
\newcommand{\og}{\mathord{>}}
\newcommand{\oeq}{\mathord{=}}
\newcommand{\op}{\mathord{+}}
\newcommand{\uif}{\mathbf{if}}
\newcommand{\uthen}{\mathbf{then}}

\zadani{10}{12.\,12.\,2011}

\noindent 
{\bf 1. [6 bodů]}
Mějme následující gramatiku:
$G = (N, \Sigma, P, V)$, kde
\[\begin{array}{rl}
N = & \{\Veta,\VVeta,\Podmet,\Predmet,\Kdo,\Koho,\Jakou,\Sloveso\}, \\
\Sigma = &\{\carka,\ktera,\zena,\ruze,\pisen,\kost,\zenu,\ruzi, \\
  & \krasnou,\tvrdou,\ostrou,\zpiva,\vidi,\vari\}\end{array}\]
\[\begin{array}{clcl}
P = 
\{& \Veta & \rightarrow & \Podmet\ \Sloveso\ \Predmet \\
\ & \VVeta & \rightarrow & \carka\ \ktera\ \Sloveso\ \Predmet \\
\ & \Podmet & \rightarrow & \Kdo \mid \Kdo\ \VVeta \carka \\
\ & \Predmet & \rightarrow & \Koho \mid \Koho\ \VVeta \mid \Jakou\ \Predmet \\
\ & \Kdo & \rightarrow & \zena \mid \ruze \mid \pisen \mid \kost \\
\ & \Koho & \rightarrow & \zenu \mid \ruzi \mid \pisen \mid \kost \\
\ & \Jakou & \rightarrow & \krasnou \mid \tvrdou \mid \ostrou \\
\ & \Sloveso & \rightarrow & \zpiva \mid \vidi \mid \vari
~~\}.\\
\end{array}\]
\begin{itemize}
\item[(a)] 
Pro gramatiku $G$ sestrojte syntaktický analyzátor metodou \textbf{shora dolů}.
Analyzujte slovo $\zena\ \carka\ \ktera\ \vari\ \tvrdou\ \kost\ \carka\ \zpiva\ \ostrou\ \pisen$.
\item[(b)]
Pro gramatiku $G$ sestrojte syntaktický analyzátor metodou \textbf{zdola nahoru}.
Analyzujte slovo $\ruze\ \carka\ \ktera\ \zpiva\ \krasnou\ \pisen\ \carka\ \zpiva\ \krasnou\ \pisen$.
\item[(c)]
Pomocí deterministické analýzy (CYK) analyzujte slovo $\zena\ \vidi\ \zenu\ \carka\ \ktera\ \vari\ \ruzi$. Pro usnadnění práce je zde k dispozici gramatika převedená na CNF:
\[G' = ( N \cup \{X,Y,Z,U,K\}, \Sigma, P', V)\text{, kde}\]
\[\begin{array}{clcl}
P' = 
\{& \Veta & \rightarrow & \Podmet\ X \\
\ & \VVeta & \rightarrow & Y Z \\
\ & \Podmet & \rightarrow & \zena \mid \ruze \mid \pisen \mid \kost \mid \Kdo\ U \\
\ & \Predmet & \rightarrow & \zenu \mid \ruzi \mid \pisen \mid \kost \mid \Koho\ \VVeta \mid \Jakou\ \Predmet \\
\ & \Kdo & \rightarrow & \zena \mid \ruze \mid \pisen \mid \kost \\
\ & \Koho & \rightarrow & \zenu \mid \ruzi \mid \pisen \mid \kost \\
\ & \Jakou & \rightarrow & \krasnou \mid \tvrdou \mid \ostrou \\
\ & \Sloveso & \rightarrow & \zpiva \mid \vidi \mid \vari \\
\ & X & \rightarrow & \Sloveso\ \Predmet\\
\ & Y & \rightarrow & \carka \\
\ & Z & \rightarrow & K X \\
\ & U & \rightarrow & W Y \\
\ & K & \rightarrow & \ktera 
~~\}.\\
\end{array}\]
\end{itemize}
\emph{Poznámka}: Dobře si všimněte, jaká je množina terminálů a neterminálů
	gramatiky, 
   zejména, že terminál je i znak \textbf{\underline{,}} (čárka).

\textbf{Odevzdávejte, prosím, každou část příkladu na zvláštním listě!}

\newpage

% K řešení můžete použít třeba následující:
% 
% \reseni{10}{12.\,12.\,2011}
% 
% \noindent\textbf{Řešení (a):}
% 
% \newpage
% 
% \reseni{10}{12.\,12.\,2011}
% 
% \noindent\textbf{Řešení (b):}
% 
% \newpage
% 
% \reseni{10}{12.\,12.\,2011}
% 
% \noindent\textbf{Řešení (c):}
% 
% \newpage
% 
\zadani{10}{12.\,12.\,2011}
 

\newcommand{\jedna}{\text{\ding{202}}}
\newcommand{\dva}{\text{\ding{203}}}
\newcommand{\pet}{\text{\ding{206}}}
\newcommand{\deset}{\text{\ding{211}}}
\newcommand{\kratky}{\textbf{\underline{10min}}}
\newcommand{\dlouhy}{\textbf{\underline{60min}}}

\noindent
{\bf 2. [2 body]}
Mějme následující jazyk nad abecedou $\{\jedna,\dva,\pet,\deset,\kratky,\dlouhy\}$:
 \[\begin{array}{rl} L = \{ x y \mid & x \in \{\kratky,\dlouhy\}^+, y \in \{\jedna,\dva,\pet,\deset\}^*, \\
& 14 \cdot \#_\kratky (x) + 22\cdot\#_\dlouhy(x) \le
 \#_\jedna(y) + 2\cdot\#_\dva(y) + 5\cdot\#_\pet(y) + 10\cdot\#_\deset(y)\}
 \end{array}\]
Sestrojte zásobníkový automat akceptující jazyk $L$. Jasně uveďte, jakým 
způsobem Váš automat akceptuje (koncovým stavem, prázdným zásobníkem).

\emph{Motivace:} 
Cílem je sestrojit automat na jízdenky. Uživatel automatu nejdříve 
zvolí počet a typ jízdenek (pomocí dvou tlačítek $\kratky$ a $\dlouhy$),
následně vhazuje mince $\jedna$, $\dva$, $\pet$,~$\deset$.
Automat vydá jízdenky (tj. akceptuje vstup), pokud je hodnota vhozených
mincí větší nebo rovná hodnotě jízdenek (desetiminutová jízdenka stojí
14 korun, hodinová stojí 22). Automat nevrací.

\end{document}
