Please write your solutions as clearly and concisely as possible.

1. (40 pts) Consider the regular expression

   (a(a+b)^*b + a)^*b^*

   Give the minimum-state automaton recognizing the language described by this expression.

   Hint: First construct a FA M recognizing the language (possibly using the metod described in class: first the NFA-lambda, then a NFA, then a FA) and then minimize M using the algorithm seen in the last lecture.

2. (40 pts) Consider the following automaton M = (Q,Sigma,q₀,A,delta), where: Q = {0,1,2,3,4} (set of states), Sigma = {a,b} (alphabet), A = {0} (acceptance states), q₀ = 0 (initial state), and delta is defined as follows:
   • delta(0,a) = 1, delta(0,b) = 2
   • delta(1,a) = 2, delta(1,b) = 3
   • delta(2,a) = 2, delta(2,b) = 4
   • delta(3,a) = 0, delta(3,b) = 4
   • delta(4,a) = 4, delta(4,b) = 2
   1. Give the regular expression describing the language M(L).
   2. Give the partition associated to the indistinguishability relation for this language.
   3. Say whether or not M is the minimum-state automaton recognizing L(M). In the positive case, prove that M is indeed the minimum-state automaton. In the negative case, construct the minimum-state automaton.

3. (20 pts) Consider the language

   L = {a^mbⁿc^p| n = m + p, and m, p > 0 }

   Is this langauge regular? Justify formally the answer.

   ---