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

% vim: spell spelllang=cs

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

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


\newcommand{\nonterm}[1]{\texttt{$\langle$#1$\rangle$}}
\newcommand{\nvar}{\nonterm{var}}
\newcommand{\nindex}{\nonterm{index}}
\newcommand{\nasgt}{\nonterm{asgt}}
\newcommand{\nstm}{\nonterm{stm}}
\newcommand{\nseq}{\nonterm{seq}}
\newcommand{\nprg}{\nonterm{prg}}

\newcommand{\term}[1]{\texttt{#1}}
\newcommand{\tx}{\term{x}}
\newcommand{\tzero}{\term{0}}
\newcommand{\tone}{\term{1}}
\newcommand{\tasgn}{\term{:=}}
\newcommand{\tplus}{\term{+}}
\newcommand{\twhile}{\term{while}}
\newcommand{\tneq}{\term{!=}}
\newcommand{\tsc}{\term{;}}
\newcommand{\tbegin}{\term{begin}}
\newcommand{\tend}{\term{end}}

\newcommand{\nonterms}{\nvar, \nindex, \nasgt, \nstm, \nseq, \nprg}
\newcommand{\terms}{\tx, \tzero, \tone, \tasgn, \tplus, \twhile, \tneq, \tsc, \tbegin, \tend}

\newcommand{\smlnum}[1]{\text{\scriptsize(#1)}\ }

\begin{document}
\begin{zadani}
    Uvažte následující bezkontextovou gramatiku $G$ generující \texttt{while} programy
    používané v teorii vyčíslitelnosti:

  $$ G = (\set{\nonterms}, \set{\terms}, P, \nprg)$$
  \vspace{-30pt}
  \begin{align*}
  P &= \{ \\
    & \smlnum{1} \nvar \to \tx \nindex,                         && \smlnum{7} \nstm \to \twhile\ \nvar\ \tneq\ \nvar\ \nstm, \\
    & \smlnum{2} \nindex \to \eps,                              && \smlnum{8} \nstm \to \nprg, \\
    & \smlnum{3} \nindex \to \tone \nindex,                     && \smlnum{9} \nseq \to \nstm, \\
    & \smlnum{4} \nasgt \to \nvar \tasgn\ \tzero,               && \smlnum{10} \nseq \to \nseq \tsc\ \nstm, \\
    & \smlnum{5} \nasgt \to \nvar \tasgn\ \nvar\ \tplus\ \tone, && \smlnum{11} \nprg \to \tbegin\ \tend, \\
    & \smlnum{6} \nstm \to \nasgt                               && \smlnum{12} \nprg \to \tbegin\ \nseq\ \tend \\
  \}.
  \end{align*}

  \noindent
  \begin{enumerate}[a)]
      \item Uveďte pro gramatiku $G$ syntaktický analyzátor \emph{shora dolů}.
      \item Analyzujte pomocí něj slovo $\tbegin\ \twhile\ \tx\ \tneq\ \tx\ \tbegin\ \tend\ \tend$
  \end{enumerate}

  \noindent
  Zapište celý postup výpočtu analyzátoru (vizte definici 3.37 ze skript). K
  přechodům mezi stavy výpočtu pište čtená písmena
  $\left( \turnstile{\textit{čtené písmeno}}{}\right)$.
  Pokud použitý přechod odpovídá nějakému pravidlu gramatiky $G$, napište také
  číslo pravidla, které jste v daném kroku použili
  $\left(\turnstile{\eps}{\textit{(číslo pravidla)}}\right)$.
\end{zadani}

\begin{reseni}
%%% SEM PISTE SVE RESENI

Jak vysázet přechodovou funkci:
\[
\begin{array}{rlcl}
  & \delta(q, x, X) &=& \set{(p, XX)}, \\
\end{array}
\]

Jak vysázet krok analýzy:
\[
\begin{array}{rrrr}
  {}                     & \big{(} q, & xyz ,\ & xX \big{)} \\
  \turnstile{x}{}        & \big{(} q, &  yz ,\ & X \big{)} \\
  \turnstile{\eps}{(3)}  & \big{(} q, &  yz ,\ & XX \big{)} \\
\end{array}
\]

\end{reseni}

\end{document}
