equal
deleted
inserted
replaced
11 \begin{document} |
11 \begin{document} |
12 |
12 |
13 \section*{Homework 7} |
13 \section*{Homework 7} |
14 |
14 |
15 \begin{enumerate} |
15 \begin{enumerate} |
16 \item Suppose the following finite deterministic automaton over the alphabet $\{0, 1\}$. |
16 \item Suppose the following grammar for positive numbers |
17 |
17 |
18 \begin{center} |
18 \begin{center} |
19 \begin{tikzpicture}[scale=2, line width=0.5mm] |
19 |
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} |
20 \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 |
21 |
38 \item Consider the following grammar |
22 \item Consider the following grammar |
39 |
23 |
40 \begin{center} |
24 \begin{center} |
41 \begin{tabular}{l} |
25 \begin{tabular}{l} |