### 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.

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)