65 \path[->] (q0) edge node[above] {$a$} (q1) |
65 \path[->] (q0) edge node[above] {$a$} (q1) |
66 (q1) edge [loop right] node {$b$} (); |
66 (q1) edge [loop right] node {$b$} (); |
67 \end{tikzpicture} |
67 \end{tikzpicture} |
68 \end{center} |
68 \end{center} |
69 |
69 |
70 \item Given the following deterministic finite automaton over the |
|
71 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
|
72 case states can be merged, state clearly which states can be merged. |
|
73 |
70 |
74 \begin{center} |
|
75 \begin{tikzpicture}[scale=2, line width=0.7mm] |
|
76 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
77 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
78 \node[state, accepting] (q4) at ( 2,1) {$q_4$}; |
|
79 \node[state] (q2) at (0.5,0) {$q_2$}; |
|
80 \node[state] (q3) at (1.5,0) {$q_3$}; |
|
81 \path[->] (q0) edge node[above] {$0$} (q1) |
|
82 (q0) edge node[right] {$1$} (q2) |
|
83 (q1) edge node[above] {$0$} (q4) |
|
84 (q1) edge node[right] {$1$} (q2) |
|
85 (q2) edge node[above] {$0$} (q3) |
|
86 (q2) edge [loop below] node {$1$} () |
|
87 (q3) edge node[left] {$0$} (q4) |
|
88 (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0) |
|
89 (q4) edge [loop right] node {$0, 1$} (); |
|
90 \end{tikzpicture} |
|
91 \end{center} |
|
92 |
71 |
93 %\item Given the following deterministic finite automaton |
72 %\item Given the following deterministic finite automaton |
94 % |
73 % |
95 %\begin{center} |
74 %\begin{center} |
96 %\begin{tikzpicture}[scale=3, line width=0.7mm] |
75 %\begin{tikzpicture}[scale=3, line width=0.7mm] |
122 (q0) edge [loop below] node[below] {$a$} () |
101 (q0) edge [loop below] node[below] {$a$} () |
123 (q1) edge node[above] {$a$} (q2); |
102 (q1) edge node[above] {$a$} (q2); |
124 \end{tikzpicture} |
103 \end{tikzpicture} |
125 \end{center} |
104 \end{center} |
126 |
105 |
|
106 \item Given the following deterministic finite automaton over the |
|
107 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
|
108 case states can be merged, state clearly which states can be merged. |
|
109 |
|
110 \begin{center} |
|
111 \begin{tikzpicture}[scale=2, line width=0.7mm] |
|
112 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
113 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
114 \node[state, accepting] (q4) at ( 2,1) {$q_4$}; |
|
115 \node[state] (q2) at (0.5,0) {$q_2$}; |
|
116 \node[state] (q3) at (1.5,0) {$q_3$}; |
|
117 \path[->] (q0) edge node[above] {$0$} (q1) |
|
118 (q0) edge node[right] {$1$} (q2) |
|
119 (q1) edge node[above] {$0$} (q4) |
|
120 (q1) edge node[right] {$1$} (q2) |
|
121 (q2) edge node[above] {$0$} (q3) |
|
122 (q2) edge [loop below] node {$1$} () |
|
123 (q3) edge node[left] {$0$} (q4) |
|
124 (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0) |
|
125 (q4) edge [loop right] node {$0, 1$} (); |
|
126 \end{tikzpicture} |
|
127 \end{center} |
|
128 |
127 \item Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
129 \item Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
128 |
130 |
129 \begin{center} |
131 \begin{center} |
130 \begin{tikzpicture}[scale=2, line width=0.5mm] |
132 \begin{tikzpicture}[scale=2, line width=0.5mm] |
131 \node[state, initial, accepting] (q0) at ( 0,1) {$q_0$}; |
133 \node[state, initial, accepting] (q0) at ( 0,1) {$q_0$}; |