When you are asked to define, construct or build 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.
(1p) [AB] Give an informal, intuitive description of the language accepted by the following DFA:
| a | b | c | |
|---|---|---|---|
| → s₀ | s₁ | s₀ | s₂ |
| s₁ | s₂ | s₁ | s₁ |
| * s₂ | s₂ | s₂ | s₂ |
As an example, for the language {wb | w ∈ {a, b, c}*} you could write something like “words that contain a’s, b’s and c’s, and end with a b”.
[AB] In this exercise the alphabet Σ = {a, b}.
(1p) Define a DFA A over Σ such that L(A) = {w ∈ Σ* | ∄u, v ∈ Σ*. w = ubbav} (i.e. the DFA should accept exactly those strings that do not contain substrings of the form bba).
(1p) Define a DFA B over Σ that accepts exactly those strings that have an even number of occurrences of a.
(2p) Construct A ⊗ B, i.e. use the product construction to build an automaton that accepts the language L(A) ∩ L(B).
[AB] In this exercise the alphabet Σ = {a, b}.
(3p) Define an NFA A (without ε-transitions) over Σ such that L(A) = M ∪ N, where M = {w ∈ Σ* | ∃u, v ∈ Σ*. w = ubaav} and N contains exactly those strings in Σ* where every occurrence of a is directly followed by two or more occurrences of b.
(2p) Use the subset construction to build a corresponding DFA. You are allowed to omit inaccessible states.
(Exercises marked with [AB] are based on exercises from a previous version of this course, given by Ana Bove.)