Fall 2000, CSE 468: Assignment 2


Distributed: Published on the web on Sep 22.
Due: Oct 4 (in class).
Total maximum score: 100 points.

The purpose of this assignment is to to provide experience with recognition of regular expressions via finite automata.

Please write your solutions as clearly and concisely as possible.


Consider the language L on the alphabet {a,b} containing all the strings that have as suffix the string bb followed by an arbitrary number of a's. Formally:
L = {x in {a,b}*| exists y in {a,b}* and exists n such that x = ybban}
  1. Define L as a regular expression.
  2. Define a NFA-lambda M recognizing L, following the method seen in class (also explained in Martin's book, paragraph 4.3).
  3. Define a NFA M' recognizing L. You can derive M' from M using the method seen in class, or, if you find it more convenient, you can define M' directly. (In general the direct definition allows to contruct a NFA with less states)
  4. Derive from M' a FA M'' recognizing L, by applying the method seen in class.
  5. Write a program in your favourite language (among C, C++, Java, ML, Prolog, or Pascal) implementing the automaton M''. The program must take in input strings on the alphabet {a,b}, and answer "accept" or "reject" depending on whether the given string belongs to L or not. The program must simulate the automaton in the sense that it must have an internal representation of the states of the automaton and a way of representing the current state, it must take in input the symbols of the string one by one, and for each symbol read it should make a transition from the current state to the next state as defined in the automaton. Use a character not in the alphabet, say c, to represent the end of the input.
  6. Show that your program gives the correct answers on the following inputs:
    1. bbc     (accept)
    2. aabc       (reject)
    3. aabbac         (accept)
    4. aabbabac           (reject)
    5. aabbabbac             (accept)

Please use diagrams to represent automata (as usual), and add comments to the program to help me understanding it.

Please keep the file with the program: I might need to test it.