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 7}

    14 

    15 \begin{enumerate}

    16 \item Suppose the following finite deterministic automaton over the alphabet $\{0, 1\}$.

    17 

    18 \begin{center}

    19 \begin{tikzpicture}[scale=2, line width=0.5mm]

    20   \node[state, initial, accepting]        (q0) at ( 0,1) {$q_0$};

    21   \node[state, accepting]                    (q1) at ( 1,1) {$q_1$};

    22  \node[state] (q2) at ( 2,1) {$q_2$};

    23   \path[->] (q0) edge[bend left] node[above] {$0$} (q1)

    24                   (q1) edge[bend left] node[above] {$1$} (q0)

    25                   (q2) edge[bend left=50] node[below] {$1$} (q0)

    26                   (q1) edge node[above] {$0$} (q2)

    27                   (q2) edge [loop right] node {$0$} ()

    28                   (q0) edge [loop below] node {$1$} ()

    29             ;

    30 \end{tikzpicture}

    31 \end{center}

    32 

    33 Give a regular expression that can recognise the same language as

    34 this automaton. (Hint: If you use Brzozwski's method, you can assume

    35 Arden's lemma which states that an equation of the form $q = q\cdot r + s$

    36 has the unique solution $q = s \cdot r^*$.)

    37 

    38 \item Consider the following grammar 

    39 

    40 \begin{center}

    41 \begin{tabular}{l}

    42 $S \rightarrow N\cdot P$\\

    43 $P \rightarrow V\cdot N$\\

    44 $N \rightarrow N\cdot N$\\

    45 $N \rightarrow A \cdot N$\\

    46 $N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\

    47 $V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\

    48 $A \rightarrow \texttt{The} \;|\; \texttt{the}$\\

    49 \end{tabular}

    50 \end{center}

    51 

    52 where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals.

    53 Using the CYK-algorithm, check whether or not the following string can be parsed

    54 by the grammar:

    55 

    56 \begin{center}

    57 \texttt{The trainer trains the student team}

    58 \end{center}

    59 

    60 \item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, 

    61 \texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example

    62 \texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible!

    63 See:

    64 

    65 \begin{center}

    66 \url{http://callumacrae.github.com/regex-tuesday/challenge11.html}

    67 \end{center}

    68 \end{enumerate}

    69 

    70 \end{document}

    71 

    72 %%% Local Variables: 

    73 %%% mode: latex

    74 %%% TeX-master: t

    75 %%% End: