\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 as+
−
this automaton. (Hint: If you use Brzozwski's method, you can assume+
−
Arden'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 parsed+
−
by 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: +
−