CPSC 215L  Lab 3: Deterministic Finite Automata

			Due Thursday 9/23/99



  This lab asks you to implement finite state machines using a
2-dimensional array as described in class. For simplicity we'll
confine ourselfs to strings with only lower-case alphabetical letters,
but your program should not crash if it gets a string with other
characters.


1.  Implement a class "DFA" using the following template:

class DFA      // deterministic finite automaton class
{
  int numstates, alphasize;	// # of states, chars, set by constructor
  int[][] Table;		// state transition table
  int initstate, acceptstate;

  DFA(int n, int a) 		// constructor, sets table dimensions
   { Table = new int[n][a];     // initial contents all 0's
     numstates = n;  alphasize = a;
   }

// you must be able to handle the case when the following function
// returns a negative number, which is not a valid array index:
  int convert(char c)  		// converts char into valid array index
   { return ( (int) c) - ( (int) 'a'); }


/* You define the following "accept" method that takes a string, follows
   the table and return true if the S is accepted by the state machine, and
   false if not.  In addition, it should print messages indicating the
   current state and the current character it's reading (see below).
*/

public boolean accept(String S)
{/* follow the table...  */}

} // end class DFA


/* Here's the coding of the machine that accepts an odd number of 'a's, and
   how you should test your program:
*/

public class finitestates
{

public static void main(String[] args)
{ boolean accepted;
  DFA EO = new DFA(3,3);	// "EO" is the EVEN-ODD state machine
  int ODD = 1;     // constant for odd state;
  int EVEN = 2;    // constant for even state;
  EO.acceptstate = ODD;
  EO.initstate = EVEN;
  // fill in transition table:
  EO.Table[EVEN][EO.convert('a')] = ODD;
  EO.Table[EVEN][EO.convert('b')] = EVEN;
  EO.Table[ODD][EO.convert('a')] = EVEN;
  EO.Table[ODD][EO.convert('b')] = ODD;

  accepted = EO.accept("ababa");   // runs machine
  if (accepted) System.out.println("String accepted.") 
	else System.out.println("String not accepted.");
} // end main


}// end class finitestates


/* The above main method should produce output that should look similar
   to the following:
*/

Current state = 2.  Input symbol = a
Current state = 1.  Input symbol = b
Current state = 1.  Input symbol = a
Current state = 2.  Input symbol = b
Current state = 2.  Input symbol = a
Current state = 1.  End of String

String accepted.


/* --------------------------------------------------------- */

Make sure you can handle inputs that are not in your alphabet - this means
you have to check if the number you get using the 'convert' method 
is a valid array index (not negative and not too large).  The length
of a string S is "S.length()".  The character at position P is 
"S.charAt(P)".  The first character is at position 0.  Demonstrate your
program on several strings, both with and without an odd number of 'a's.
Also use examples with characters other than 'a' or 'b' or alphabetical
characters.

After you get your program to work for the above example, do the following:


1. Device a deterministic finite automaton that accepts any string with
   'a's and 'b's that embed EITHER the sequence "aaa" OR the sequence "bbb".
   DRAW IT ON PAPER FIRST (turn in diagram as part of lab).

2. Code this state machine as an instance of the class DFA.

3. Test it on several examples to make sure it works correctly.  Use the
   following method to test your solution on 100 randomly generated Strings,
   each with a maximum length of 8 characters. Your lab should include 
   output showing that each string was accepted/rejected correctly.

// it's up to you to figure out where and how to use this:
public String randomString(int maxlength)
 {  String S;
    int length = ((int) (Math.random() * maxlength)) + 1;
    for (int i=0;i<length;i++)
     {  if ( ((int) (Math.random() * 2)) == 0)  S = S + "a";
		else S = S + "b";
     } // end for loop
    return S;
 }