When you are asked to define an automaton, give the automaton in a separate file. Use one of the following file formats:
Explanations can be given either in the file containing the automaton (if this is suitable), or in the main file.
(3p) [AB] Prove that a*(b + ab*) = b + aa*b*.
(2p) Prove that every non-regular language over an alphabet Σ has an infinite complement (with respect to Σ*).
Hint: Use one of the closure properties for regular languages.
(3p) [AB] Show that the language {w ∈ {0, 1, 2}* | #0(w) + #1(w) = #2(w)} over the alphabet {0, 1, 2} is not regular by using the pumping lemma for regular languages. Here #a(w) is the number of occurrences of a in w.
(2p) [AB] Minimise the following DFA:
| 0 | 1 | |
|---|---|---|
| → * s₀ | s₁ | s₃ |
| s₁ | s₄ | s₂ |
| * s₂ | s₁ | s₅ |
| s₃ | s₀ | s₄ |
| s₄ | s₄ | s₄ |
| s₅ | s₂ | s₄ |
Do not just give an answer, show step by step how you construct the minimised DFA.
(Exercises marked with [AB] are based on exercises from a previous version of this course, given by Ana Bove.)