Finite Automata

Finite Automata are mathematical devices that define a class of languages called "regular" languages. The regular languages are defined over an alphabet, usually a 2-symbol alphabet { a, b }. These languages are nothing but sets of strings made up of the letters of the alphabet. Some examples of regular languages are:

L1 = { abaa, aabb, abbbba }
L2 = { w | w is a string of a's and b's with an even number of a's and an odd number of b's }
L3 = { w | w is a string of a's and b's which start with an a and end with a b }

Finite automata play an important role in Computer Science and we shall write Python programs to operate them. They come in two varieties:

Deterministic Finite Automata (DFA): A deterministic finite automata consists of a set of states, one of which is the "start" state and some of them are designated as "final" states. There are transitions from states to states on a symbol from the alphabet. In a DFA there must be a transition from every state on every symbol from the alphabet. Here is an example of a DFA:

alphabet a b
states q0 q1
start q0
final q1
trans q0:a:q1
trans q0:b:q0
trans q1:a:q0
trans q1:b:q1

We can picture the DFA as follows:

The execution of a DFA works as follows: It starts in the start state as the "current" state. It has an input string, which it reads one symbol at a time. Depending on the current state and the symbol read, the DFA consults the transition table to determine which state to move to, which becomes the new "current" state. The DFA repeats this process until it has read all input symbols. At the end, if the DFA has reached a "final" state it ACCEPTS the input otherwise it REJECTS the input. Here is a sample execution of this DFA on input abaab:

   (q0,'abaab')
=> (q1,'baab')
=> (q1,'aab')
=> (q0,'ab')
=> (q1,'b')
=> (q1,'')
   ACCEPT

Non-deterministic Finite Automata (NFA): A non-deterministic finite automata consists of a set of states, one of which is the "start" state and some of them are designated as "final" states. There are transitions from states to states on a symbol from the alphabet. In an NFA there need not be a transition from every state on every symbol from the alphabet. From a state there can be zero or more transitions leading to different states on an input symbol. Here is an example of a NFA:

alphabet a b
states q0 q1 q2 q3 q4
start q0
final q2 q3 q4
trans q0:a:q1
trans q0:a:q4
trans q0:b:q3
trans q1:a:q1
trans q1:b:q2
trans q4:b:q4

We can picture the NFA as follows:

The execution of an NFA works as follows: It starts in the start state as the "current" state. It has an input string, which it reads one symbol at a time. Depending on the current state and the symbol read, the NFA consults the transition table to determine which state to move to. If there are multiple choices for the next states, the NFA chooses any one of them, which becomes the new "current" state. If there are no choices for the next state the NFA crashes. The NFA will ACCEPT the input string if there is at least ONE POSSIBLE PATH to a final state. Otherwise it REJECTS the input. Here is a sample execution of this NFA on input abb:

   (q0,'abb')
=> (q1,'bb')
=> (q2,'b')
   CRASH

   (q0,'abb')
=> (q4,'bb')
=> (q4,'b')
=> (q4,'')
   ACCEPT

TO DO: Write two Python programs, DFA.py and NFA.py, that read DFA and NFA descriptions from a file that is specified on command line and stores the descriptions in nested dictionaries as shown below for the DFA and NFA shown earlier:

  dfa_transitions = { 'q0': {'a': 'q1', 'b': 'q0'}, 
                      'q1': {'a': 'q0', 'b': 'q1'}
                    }

  nfa_transitions = { 'q0': {'a': {'q1','q4'}, 'b': {'q3'}}, 
                      'q1': {'a': {'q1'},      'b': {'q2'}}
                      'q2': {'a': {},          'b': {}}
                      'q3': {'a': {},          'b': {}}
                      'q4': {'a': {},          'b': {'q4'}}
                    }

After storing the descriptions in memory, the programs prompt the user for an input string and executes the DFA or NFA on the input and prints ACCEPT or REJECT at the end. The prompting for input must repeat until user types in e.

A sample program run for DFA.py is shown below:

ASCSC1PP629W1:solution raj$ more d0.dfa
alphabet a b
states q0 q1
start q0
final q1
trans q0:a:q1
trans q0:b:q0
trans q1:a:q0
trans q1:b:q1
ASCSC1PP629W1:solution raj$ python3 DFA.py d0.dfa 
enter string to test: abb
('q0', 'abb')
('q1', 'bb')
('q1', 'b')
('q1', '')
ACCEPT
enter string to test: aba
('q0', 'aba')
('q1', 'ba')
('q1', 'a')
('q0', '')
REJECT
enter string to test: ababaab
('q0', 'ababaab')
('q1', 'babaab')
('q1', 'abaab')
('q0', 'baab')
('q0', 'aab')
('q1', 'ab')
('q0', 'b')
('q0', '')
REJECT
enter string to test: e
Bye!
ASCSC1PP629W1:solution raj$

A sample program run for NFA.py is shown below:

ASCSC1PP629W1:solution raj$ more n3.nfa
alphabet a b
states q0 q1 q2 q3 q4
start q0
final q2 q3 q4
trans q0:a:q1
trans q0:a:q4
trans q0:b:q3
trans q1:a:q1
trans q1:b:q2
trans q4:b:q4
ASCSC1PP629W1:solution raj$ python3 NFA.py n3.nfa
enter string to test: abb
({'q0'}, 'abb')
({'q1', 'q4'}, 'bb')
({'q2', 'q4'}, 'b')
({'q4'}, '')
ACCEPT
enter string to test: bab
({'q0'}, 'bab')
({'q3'}, 'ab')
(set(), 'b')
(set(), '')
REJECT
enter string to test: e
ASCSC1PP629W1:solution raj$ 

Modular design using functions

You should modularize the program by defining several functions, such as the following for DFA.py:

read_data() - this function reads data and returns the dictionary described earlier
run_dfa() - takes DFA data structure and the input string as input and returns True/False for ACCEPT/REJECT
main() - implements the main loop and calls to above two functions

You should design similar functions for NFA.py.