\documentclass{article}\usepackage{charter}\usepackage{hyperref}\usepackage{amssymb}\usepackage{amsmath}\usepackage{tikz}\usetikzlibrary{automata}\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions\begin{document}\section*{Homework 7}\begin{enumerate}\item Suppose the following finite deterministic automaton over the alphabet $\{0, 1\}$.\begin{center}\begin{tikzpicture}[scale=2, line width=0.5mm] \node[state, initial, accepting] (q0) at ( 0,1) {$q_0$}; \node[state, accepting] (q1) at ( 1,1) {$q_1$}; \node[state] (q2) at ( 2,1) {$q_2$}; \path[->] (q0) edge[bend left] node[above] {$0$} (q1) (q1) edge[bend left] node[above] {$1$} (q0) (q2) edge[bend left=50] node[below] {$1$} (q0) (q1) edge node[above] {$0$} (q2) (q2) edge [loop right] node {$0$} () (q0) edge [loop below] node {$1$} () ;\end{tikzpicture}\end{center}Give a regular expression that can recognise the same language asthis automaton. (Hint: If you use Brzozwski's method, you can assumeArden's lemma which states that an equation of the form $q = q\cdot r + s$has the unique solution $q = s \cdot r^*$.)\item Consider the following grammar \begin{center}\begin{tabular}{l}$S \rightarrow N\cdot P$\\$P \rightarrow V\cdot N$\\$N \rightarrow N\cdot N$\\$N \rightarrow A \cdot N$\\$N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\$V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\$A \rightarrow \texttt{The} \;|\; \texttt{the}$\\\end{tabular}\end{center}where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals.Using the CYK-algorithm, check whether or not the following string can be parsedby the grammar:\begin{center}\texttt{The trainer trains the student team}\end{center}\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, \texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible!See:\begin{center}\url{http://callumacrae.github.com/regex-tuesday/challenge11.html}\end{center}\end{enumerate}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: