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.

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,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:

    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.