equal
deleted
inserted
replaced
67 \end{tabular} |
67 \end{tabular} |
68 \end{center} |
68 \end{center} |
69 |
69 |
70 What is the language recognised by this automaton? |
70 What is the language recognised by this automaton? |
71 |
71 |
72 |
72 \solution{ |
|
73 All strings consisting of 0 or more a's then 1 or more b's, |
|
74 which is equivalent to the language of the regular |
|
75 expression $a^* \cdot b \cdot b^*$. |
|
76 } |
73 |
77 |
74 \item Give a non-deterministic finite automaton that can |
78 \item Give a non-deterministic finite automaton that can |
75 recognise the language $L(a\cdot (a + b)^* \cdot c)$. |
79 recognise the language $L(a\cdot (a + b)^* \cdot c)$. |
76 |
80 |
77 \solution{It is already possible to just read off the automaton without |
81 \solution{It is already possible to just read off the automaton without |
106 |
110 |
107 Here you test whether the all states reachable (for $s$) contain at least |
111 Here you test whether the all states reachable (for $s$) contain at least |
108 a single accepting state. |
112 a single accepting state. |
109 |
113 |
110 } |
114 } |
|
115 |
|
116 |
111 |
117 |
112 \item Given the following deterministic finite automaton over |
118 \item Given the following deterministic finite automaton over |
113 the alphabet $\{a, b\}$, find an automaton that |
119 the alphabet $\{a, b\}$, find an automaton that |
114 recognises the complement language. (Hint: Recall that |
120 recognises the complement language. (Hint: Recall that |
115 for the algorithm from the lectures, the automaton needs |
121 for the algorithm from the lectures, the automaton needs |
176 (q0) edge [loop below] node[below] {$a$} () |
182 (q0) edge [loop below] node[below] {$a$} () |
177 (q1) edge node[above] {$a$} (q2); |
183 (q1) edge node[above] {$a$} (q2); |
178 \end{tikzpicture} |
184 \end{tikzpicture} |
179 \end{center} |
185 \end{center} |
180 |
186 |
|
187 \solution{ |
|
188 The DFA has three states Q0,Q1,Q2 with Q0 starting state and Q2 accepting. |
|
189 The transitions are (Q0,a)-> Q1 (Q0,b)->Q0 (Q1,a)->Q2 (Q1,b)->Q0 |
|
190 (Q2,a)->Q2 (Q2,b)->Q0. |
|
191 } |
|
192 |
181 \item %%\textbf{(Deleted for 2017, 2018, 2019)} |
193 \item %%\textbf{(Deleted for 2017, 2018, 2019)} |
182 Given the following deterministic finite automaton over the |
194 Given the following deterministic finite automaton over the |
183 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
195 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
184 case states can be merged, state clearly which states can be merged. |
196 case states can be merged, state clearly which states can be merged. |
185 |
197 |
230 Give a regular expression that can recognise the same language as |
242 Give a regular expression that can recognise the same language as |
231 this automaton. (Hint: If you use Brzozwski's method, you can assume |
243 this automaton. (Hint: If you use Brzozwski's method, you can assume |
232 Arden's lemma which states that an equation of the form $q = q\cdot r + s$ |
244 Arden's lemma which states that an equation of the form $q = q\cdot r + s$ |
233 has the unique solution $q = s \cdot r^*$.) |
245 has the unique solution $q = s \cdot r^*$.) |
234 |
246 |
|
247 \solution{ |
|
248 $(b + ab + aa(a^*)b)^* \cdot (1 + a)$ |
|
249 } |
|
250 |
235 \item If a non-deterministic finite automaton (NFA) has |
251 \item If a non-deterministic finite automaton (NFA) has |
236 $n$ states. How many states does a deterministic |
252 $n$ states. How many states does a deterministic |
237 automaton (DFA) that can recognise the same language |
253 automaton (DFA) that can recognise the same language |
238 as the NFA maximal need? |
254 as the NFA maximal need? |
239 |
255 |