Assignment 2

1. (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”.

2. [AB] In this exercise the alphabet Σ = {a, b}.

   1. (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).

   2. (1p) Define a DFA B over Σ that accepts exactly those strings that have an even number of occurrences of a.

   3. (2p) Construct A ⊗ B, i.e. use the product construction to build an automaton that accepts the language L(A) ∩ L(B).

3. [AB] In this exercise the alphabet Σ = {a, b}.

   1. (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.

   2. (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.)