\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\usepackage{graphicx}
\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}
}



\begin{document}

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

\zadani{11}{13.\,12.\,2010}

\noindent 
{\bf 1. [2 body]}
Mějme následující gramatiku:
\[G = (\{S',S,A,V,P,E,N,C,R\}, \{x,y,1,0,\ol,\og,\oeq,\uif,\uthen,
    ;,\op\}, P, S')\text{, kde}\]
\[\begin{array}{clcl}
P = 
\{& S' & \rightarrow & S';S \mid S , \\
\ & S & \rightarrow & A \mid \uif\  C\  \uthen\  S, \\
\ & A & \rightarrow & VPE , \\
\ & V & \rightarrow & x \mid y, \\
\ & P & \rightarrow & \oeq, \\
\ & E & \rightarrow & V \mid N \mid E \,\op\, E, \\
\ & N & \rightarrow & 0 \mid 1 \mid 0N \mid 1N, \\
\ & C & \rightarrow & ERE, \\
\ & R & \rightarrow & \oeq \mid \ol \mid \og ~~\}.\\
\end{array}\]
Pro gramatiku $G$ sestrojte syntaktický analyzátor metodou \textbf{shora dolů}.
Analyzujte slovo $\uif\ x > 1\ \uthen\ y = 10$.

\emph{Poznámka}: Dobře si všimněte, jaká je množina terminálů gramatiky, 
  zejména, že terminály jsou i znaky $\ol$, $\oeq$, $\og$, $;$, $\uif$ a 
  $\uthen$. U posledních dvou jsme použili tučné zvýraznění, abychom tím dali
   najevo, že jde o jeden terminál, nikoli o posloupnost dvou či čtyř terminálů.
   Bílé místo (mezery) ve slově je jen pro lepší čitelnost, mezery nepatří mezi
  terminály. 

\newpage

\zadani{11}{13.\,12.\,2010}

\noindent 
{\bf 2. [2 body]}
Mějme následující gramatiku:
\[G = (\{S',S,A,V,P,E,N,C,R\}, \{x,y,1,0,\ol,\og,\oeq,\uif,\uthen,
    ;,\op\}, P, S')\text{, kde}\]
\[\begin{array}{clcl}
P = 
\{& S' & \rightarrow & S';S \mid S , \\
\ & S & \rightarrow & A \mid \uif\  C\  \uthen\  S, \\
\ & A & \rightarrow & VPE , \\
\ & V & \rightarrow & x \mid y, \\
\ & P & \rightarrow & \oeq, \\
\ & E & \rightarrow & V \mid N \mid E \,\op\, E, \\
\ & N & \rightarrow & 0 \mid 1 \mid 0N \mid 1N, \\
\ & C & \rightarrow & ERE, \\
\ & R & \rightarrow & \oeq \mid \ol \mid \og ~~\}.\\
\end{array}\]
Pro gramatiku $G$ sestrojte syntaktický analyzátor metodou \textbf{zdola nahoru}.
Analyzujte slovo $\uif\ x > 1\ \uthen\ y = 10$.

\emph{Poznámka}: Dobře si všimněte, jaká je množina terminálů gramatiky, 
  zejména, že terminály jsou i znaky $\ol$, $\oeq$, $\og$, $;$, $\uif$ a 
  $\uthen$. U posledních dvou jsme použili tučné zvýraznění, abychom tím dali
   najevo, že jde o jeden terminál, nikoli o posloupnost dvou či čtyř terminálů.
   Bílé místo (mezery) ve slově je jen pro lepší čitelnost, mezery nepatří mezi
  terminály. 
\newpage

\zadani{11}{13.\,12.\,2010}

\noindent
{\bf 3. [2 body]}
Mějme následující jazyk nad abecedou $\{1,2,5,\oeq\}$:
\[ L = \{ x = y \mid x \in \{1,2\}^*, y \in \{5\}^*, 
\#_1(x) + 2\cdot\#_2(x) = 5\cdot\#_5(y) \}\]
Jedná se tedy o jazyk všech slov, která jsou tvaru $x = y$, kde
$x$ se skládá pouze ze znaků $1$ a $2$, $y$ jen ze znaků $5$ a 
ciferný součet $x$ a $y$ je stejný. (Všimněte si, že znak $\oeq$
patří mezi znaky abecedy!)

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).
(Motivace: jde o to, sestrojit automat, do nějž uživatel hází množství jedno-
a dvoukorun, pak zmáčkne tlačítko $\oeq$ a následně hází množství pětikorun.
Automat má rozhodnout, jestli částky vhozené před a po zmáčknutí tlačítka $\oeq$
byly stejné.)

\bigskip

\noindent
{\bf BONUS [+2 body]}: Sestrojte zásobníkový automat s jedním stavem,
akceptující jazyk~$L$.
(Stačí vyřešit bonusovou variantu, neboť ta v sobě obsahuje i řešení
 příkladu jako takového. Napíšete-li tedy správný zásobníkový automat pro $L$
 s~jedním stavem, získáte 4 body.)

\end{document}
