1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 \usepackage{tikz}

     7 \usetikzlibrary{automata}

     8 

     9 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

    10 

    11 \begin{document}

    12 

    13 \section*{Homework 8}

    14 

    15 \begin{enumerate}

    16 \item Suppose the following grammar for the WHILE-language:

    17 

    18 \begin{center}

    19 \begin{tabular}{lcl}

    20 $Stmt$ & $\rightarrow$ &  $\text{skip}$\\

    21               & $|$ & $Id := AExp$\\

    22               & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\

    23               & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\

    24 $Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\

    25               & $|$ & $Stmt$\medskip\\

    26 $Block$ & $\rightarrow$ &  $\{ Stmts \}$\\

    27                 & $|$ & $Stmt$\medskip\\

    28 $AExp$ & $\rightarrow$ & $AExp + AExp$\\

    29                & $|$ & $AExp * AExp$\\

    30                & $|$ & $( AExp )$\\

    31                 & $|$ & $Num$\\

    32                 & $|$ & $Id$\medskip\\

    33 $BExp$ & $\rightarrow$ & $AExp = AExp$\\

    34                  & $|$ & $AExp \not= AExp$\\

    35                   & $|$ & $\text{false}$\\

    36                   & $|$ & $\text{true}$\\

    37 

    38 \end{tabular}

    39 \end{center}

    40 

    41 Transform this grammar into Chomsky normalform.

    42 

    43 \item Write a program in the WHILE-language that calculates the factorial function.

    44 

    45 \end{enumerate}

    46 

    47 \end{document}

    48 

    49 %%% Local Variables: 

    50 %%% mode: latex

    51 %%% TeX-master: t

    52 %%% End: