57 complement language. (Hint: Recall that for the algorithm from the |
57 complement language. (Hint: Recall that for the algorithm from the |
58 lectures, the automaton needs to be in completed form, that is have |
58 lectures, the automaton needs to be in completed form, that is have |
59 a transition for every letter from the alphabet.) |
59 a transition for every letter from the alphabet.) |
60 |
60 |
61 \begin{center} |
61 \begin{center} |
62 \begin{tikzpicture}[scale=2, line width=0.7mm] |
62 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
63 every state/.style={minimum size=0pt, |
|
64 inner sep=2pt,draw=blue!50,very thick, |
|
65 fill=blue!20},scale=2] |
63 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
66 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
64 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
67 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
65 \path[->] (q0) edge node[above] {$a$} (q1) |
68 \path[->] (q0) edge node[above] {$a$} (q1) |
66 (q1) edge [loop right] node {$b$} (); |
69 (q1) edge [loop right] node {$b$} (); |
67 \end{tikzpicture} |
70 \end{tikzpicture} |
90 \item Given the following non-deterministic finite automaton over the |
93 \item Given the following non-deterministic finite automaton over the |
91 alphabet $\{a, b\}$, find a deterministic finite automaton that |
94 alphabet $\{a, b\}$, find a deterministic finite automaton that |
92 recognises the same language: |
95 recognises the same language: |
93 |
96 |
94 \begin{center} |
97 \begin{center} |
95 \begin{tikzpicture}[scale=3, line width=0.7mm] |
98 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
99 every state/.style={minimum size=0pt, |
|
100 inner sep=2pt,draw=blue!50,very thick, |
|
101 fill=blue!20},scale=2] |
96 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
102 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
97 \node[state] (q1) at ( 1,1) {$q_1$}; |
103 \node[state] (q1) at ( 1,1) {$q_1$}; |
98 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
104 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
99 \path[->] (q0) edge node[above] {$a$} (q1) |
105 \path[->] (q0) edge node[above] {$a$} (q1) |
100 (q0) edge [loop above] node[above] {$b$} () |
106 (q0) edge [loop above] node[above] {$b$} () |
106 \item Given the following deterministic finite automaton over the |
112 \item Given the following deterministic finite automaton over the |
107 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
113 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
108 case states can be merged, state clearly which states can be merged. |
114 case states can be merged, state clearly which states can be merged. |
109 |
115 |
110 \begin{center} |
116 \begin{center} |
111 \begin{tikzpicture}[scale=2, line width=0.7mm] |
117 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
118 every state/.style={minimum size=0pt, |
|
119 inner sep=2pt,draw=blue!50,very thick, |
|
120 fill=blue!20},scale=2] |
112 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
121 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
113 \node[state] (q1) at ( 1,1) {$q_1$}; |
122 \node[state] (q1) at ( 1,1) {$q_1$}; |
114 \node[state, accepting] (q4) at ( 2,1) {$q_4$}; |
123 \node[state, accepting] (q4) at ( 2,1) {$q_4$}; |
115 \node[state] (q2) at (0.5,0) {$q_2$}; |
124 \node[state] (q2) at (0.5,0) {$q_2$}; |
116 \node[state] (q3) at (1.5,0) {$q_3$}; |
125 \node[state] (q3) at (1.5,0) {$q_3$}; |
127 \end{center} |
136 \end{center} |
128 |
137 |
129 \item Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
138 \item Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
130 |
139 |
131 \begin{center} |
140 \begin{center} |
132 \begin{tikzpicture}[scale=2, line width=0.5mm] |
141 \begin{tikzpicture}[scale=2,>=stealth',very thick,auto, |
|
142 every state/.style={minimum size=0pt, |
|
143 inner sep=2pt,draw=blue!50,very thick, |
|
144 fill=blue!20}] |
133 \node[state, initial, accepting] (q0) at ( 0,1) {$q_0$}; |
145 \node[state, initial, accepting] (q0) at ( 0,1) {$q_0$}; |
134 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
146 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
135 \node[state] (q2) at ( 2,1) {$q_2$}; |
147 \node[state] (q2) at ( 2,1) {$q_2$}; |
136 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
148 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
137 (q1) edge[bend left] node[above] {$b$} (q0) |
149 (q1) edge[bend left] node[above] {$b$} (q0) |