diff -r 9ce2414e470e -r b17eff695c7f hws/hw07.tex --- a/hws/hw07.tex Mon Nov 11 00:34:14 2013 +0000 +++ b/hws/hw07.tex Mon Nov 11 13:48:34 2013 +0000 @@ -13,28 +13,12 @@ \section*{Homework 7} \begin{enumerate} -\item Suppose the following finite deterministic automaton over the alphabet $\{0, 1\}$. +\item Suppose the following grammar for positive numbers \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}