Fall 98, CSE 468: Assignment 2

Distributed: Published on the web on Sep 28.
Due: Oct 9 (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 regular expression
(aa + b)*(cc + b)*
Let L be the language represented by the above expression. Define a finite automaton recognizing L, and write a program in your favourite language (among C, C++, Java, ML, Prolog, or Pascal) implementing the automaton. Namely, the program must take in input strings on the alphabet {a,b,c}, 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 examine the characters of the input string one by one, and make a transition from the current state to the next current state as defined in the automaton.

Hint: First construct a NFA (possibly with lambda transitions) accepting L, and then derive an equivalent FA by using the method explained in class (and in the book).

The solution will consist of the definition of the FA (and all the intermediate NFA if used), the program, and the answers of the program on the following inputs:

  1. lambda (empty string)
  2. aab
  3. aabc
  4. aabaacc
  5. aaccaa
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.