Please write your solutions as clearly and concisely as possible.

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

2. (15 pts) Given a generic regular expression E and a generic finite automaton M, is it decidable whether M recognizes the language specified by E, i.e. whether L(M)=L(E)? Justify the answer. Namely, give a decision algorithm for the above property, or show that such an algoritm cannot exist.

3. (15 pts) Consider the language

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

   Is this langauge regular? Justify formally the answer.

4. (40 pts) Consider all possible regular expressions on a given alphabet Sigma = {a₁,a₂,...,a_n}. Each of these expressions is a string on the alphabet Tau = {Emptyset, Lambda,a₁,a₂,...,a_n,+,^*,(,)}, and therefore the set of these expression is a language L. Note: here Lambda is a symbol representing the regular expression denoting the empty string; it should not be confused with the empty string in Tau^*.
   1. Is it possible to represent L as a regular expression (over Tau)? Justify formally the answer.
   2. Give a non ambiguous context-free grammar for L, representing the following conventions for associativity and precedence: concatenation is right associative, + is left associative, concatenation has precedence over +, and ^* has precedence over concatenation.

      Note: "concatenation is right associative" means that an expression of the form E₁E₂E₃ is considered structured as E₁(E₂E₃).
      "+ is left associative" means that an expression of the form E₁+E₂+E₃ is considered structured as (E₁+E₂)+E₃.

   ---