CS 1MD3 - Winter 2006 - Assignment #4

Generated for Student ID: 0465698

Due Date: Friday, March 17th

(You are responsible for verifying that your student number is correct!)
NOTE: All submissions must be plain text format in ".py" files.
Here is your state transition table (in human-readable format) representing a finite state automaton:

	a	b	p	q	t
1	4	4			5
2		3	3		2
3	4	3
4	4	1		3	3
5	3		1		3

Interpretation of the table:

The top row of the table contains the alphabet of symbols.
The leftmost column contains the states of the automaton.
If the automaton is in state, s, and consumes the symbol, x, it will advance to the state listed in row s and column x.
The start state is 1.
The set of final states is {5}.

Question 1: Write a Python function which accepts a dictionary representation of a state transition table (like the one below) and an input string. The function returns True if string would be accepted by the finite state automaton represented by the state transition table, and False if it would be rejected.

Question 2: Write a Python function which accepts an input string and uses 'if' statements to determine whether the string would be accepted by the finite state automaton represented by your state transition table. Do not use a dictionary for this one.

Question 3: Write several test cases for each of your functions involving strings which are accepted and strings which are rejected. You may use PyUnit if you feel so inspired, or just a simple Python program. If your particular machine either accepts all strings or rejects all strings, please explain why (in lieu of writing impossible test cases). If you like, you can put all three questions in one Python program. Just please, Please, PLEASE submit only plain text files with a ".py" extension!

"Free Gift" (whatever that redundancy is supposed to mean)
Here is the Python code which creates a dictionary representing your state transition table:

transDict = {(1, 't'): 5, (1, 'b'): 4, (3, 'b'): 3, (3, 'a'): 4, (5, 'p'): 1, (2, 't'): 2, (4, 'q'): 3, (2, 'b'): 3, (5, 't'): 3, (4, 'b'): 1, (4, 't'): 3, (5, 'a'): 3, (1, 'a'): 4, (2, 'p'): 3, (4, 'a'): 4}

Bonus Question:
Write a Python function which accepts a state transition table (as a dictionary), a start state, and a set of final states. The function should return True if there exists an input string that would cause the corresponding automaton to enter a state in which it has already been. In other words, determine whether the machine can "loop." Be sure to provide test cases (i.e. values for the parameters which result in True, and values which result in False).