### Fall 2000, CSE 468: Assignment 3

Distributed: Published on the web on Sat 7 Oct.
Due: Oct 18 (in class).
Total maximum score: 100 points.

The purpose of this assignment is to to provide experience with regular languages, finite automata, and minimalization of FA.

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,q0,A,delta), where: Q = {0,1,2,3,4} (set of states), Sigma = {a,b} (alphabet), A = {0} (acceptance states), q0 = 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 = {ambncp| n = m + p, and m, p > 0 }
Is this langauge regular? Justify formally the answer.