CS 1MD3 - Winter 2006 - Assignment #4
Generated for Student ID: 0570080
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 | | 3 | 1 | 1 | 1 |
2 | 4 | 3 | 3 | | |
3 | 1 | | 2 | 3 | 2 |
4 | | 3 | 3 | 2 | 2 |
5 | 4 | 3 | 1 | | 2 |
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'): 1, (4, 't'): 2, (1, 'b'): 3, (5, 'a'): 4, (3, 'a'): 1, (5, 'p'): 1, (1, 'q'): 1, (4, 'p'): 3, (1, 'p'): 1, (3, 't'): 2, (2, 'a'): 4, (2, 'b'): 3, (5, 't'): 2, (4, 'b'): 3, (3, 'q'): 3, (3, 'p'): 2, (4, 'q'): 2, (2, 'p'): 3, (5, 'b'): 3}
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).