equal
deleted
inserted
replaced
171 this automaton. (Hint: If you use Brzozwski's method, you can assume |
171 this automaton. (Hint: If you use Brzozwski's method, you can assume |
172 Arden's lemma which states that an equation of the form $q = q\cdot r + s$ |
172 Arden's lemma which states that an equation of the form $q = q\cdot r + s$ |
173 has the unique solution $q = s \cdot r^*$.) |
173 has the unique solution $q = s \cdot r^*$.) |
174 |
174 |
175 \item If a non-deterministic finite automaton (NFA) has |
175 \item If a non-deterministic finite automaton (NFA) has |
176 $n$ states. How many states does a deterministic |
176 $n$ states. How many states does a deterministic |
177 automaton (DFA) that can recognise the same language |
177 automaton (DFA) that can recognise the same language |
178 as the NFA maximal need? |
178 as the NFA maximal need? |
179 |
179 |
|
180 \item Prove that for all regular expressions $r$ we have |
|
181 |
|
182 \begin{center} |
|
183 $\textit{nullable}(r) \quad \text{if and only if} |
|
184 \quad [] \in L(r)$ |
|
185 \end{center} |
|
186 |
|
187 Write down clearly in each case what you need to prove |
|
188 and what are the assumptions. |
|
189 |
|
190 |
180 \item \POSTSCRIPT |
191 \item \POSTSCRIPT |
181 \end{enumerate} |
192 \end{enumerate} |
182 |
193 |
183 \end{document} |
194 \end{document} |
184 |
195 |