CS 451/LLC Lab 5: Regular Expressions and Finite Automata

Due Monday 20 March 2006

This assignment will consist of written parts and a programming project; we'll grade the written parts in lab as a kind of discussion section, in sthe style of some WU math classes (and occasionally the algorithms course). Be prepared to present your solution at the board and to compare it to others' solutions to the same exercise.

For the programming parts, work in Java or any language of your choice (Haskell would be OK, but let's not push it unless you want to).

Hey, here are the test DFAs!

Exercises

1. For each of the following English descriptions, find an RE whose language fits the description:
   1. over the alphabet {a,b}, strings that start with an 'a' and end with an 'a', but are otherwise unrestricted;
   2. over the alphabet {a,b}, strings that have no more than two 'b's in them (but otherwise unrestricted);
   3. over the alphabet {a,b,c}, strings that start with an 'a' and end with an 'a', and have only a single 'b' between these two (but otherwise unrestricted);

2. For each of the English descriptions above, find a DFA which will "implement" the corresponding language:
   1. draw a picture (transition diagram) for each of theese DFAs;
   2. express each DFA as a 5-tuple in set-theoretic meta-language (you may express the transition function as a table).

3. Give a formal definition of the reverse of a DFA (intuitively, it should involve the reversal of arrows in the original, and it should accept a language whose members are each the reverse of a string in the language of the original DFA). Your definition should define one set-theoretic DFA (the reversed one) in terms of another (the original).

4. Argue informally why the language of palindromes over the alphabet {a,b} cannot be a regular language (palindromes read the same forwards and backwards: a language of palindromes has only palindromes in it).

5. Implement (in Java, etc.) a program which will transform a DFA into a regular expression; see this page and following for hints on how to do this (also see below).

Hints on implementing the transformation in Java

• you'll need a type for REs, so ithat you can construct them as needed: use an abstract class for REs in general, and extend it several times for each possible case of RE (null, epsilon, etc.). In the recursive cases you will have two RE components (references to them) called (e.g.) left and right. The natural methods on these would include one to print out an RE.

• you'll need a type for GNFAs: this is basically a matrix of regular expressions, one for the transition from each state to any other state (except no incoming transitions to the initial state, and no out-going transitions from the single final state). Another way to think of this is as a function from pairs (state cross state) to a regular expression.

  So a GNFA is a tuple <A,S,d,i,f> where:

  • A is an alphabet;
  • S is a state set;
  • i and f are states in S;
  • d is a transtition function ∈ (S \ {f}) × (S \ {i}) → RE
• if you like, you might use a type for DFAs and a method to convert each DFA into a GNFA, so that you can "inject" the original DFA into a GNFA. This would keep you honest about the conversion and shouldn't be too hard (the DFA is as described in lecture and hand-outs; i.e., like above, but with a set of final states (rather than one) and the transition function is in S × A → S.