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}
- Define L as a regular expression.
- Define a NFA-lambda M recognizing L, following the method seen in class
(also explained in Martin's book, paragraph 4.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)
- Derive from M' a FA M'' recognizing L,
by applying the method seen in class.
- 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.
- Show that your program gives the correct answers on the
following inputs:
- bbc (accept)
- aabc (reject)
- aabbac (accept)
- aabbabac (reject)
- 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.