Pushdown Automata

A Pushdown Automata is a mathematical device that defines a class of languages called "context-free" languages. Context-free 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 context-free 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 }
L4 = { w | w is a string of a's and b's which start with an n a's and ends with n b's, where n >= 0 }

Pushdown automata play an important role in Computer Science and we shall write Python programs to operate them.

Deterministic pushdown Automata (DPDA): A deterministic pushdown automata consists of a set of states, one of which is the "start" state and one of them is designated as the "final" state. In addition to the reading from input, DPDAs have the ability to manipulate a "stack" of symbols. A stack is basically a list in which symbols can be added or removed from one end only. For simplicity, we will assume that the items are added or removed from the beginning/front of the list. Adding a symbol to the front is called a "push" operation and removing an item from the front is called the "pop" operation. The transitions in a DPDA are from states to states on a symbol from the alphabet. In a DPDA, the transition may also push or pop a symbol on stack. It is possible for the transition to not push or pop from stack, in which case it leaves the stack as is. Unlike finite automata, there are no transitions out from the final state. DPDAs are deterministic in that there is at most one choice at each state for each symbol. The following is a description of a DPDA:

alphabet a b
states q0 q1 q2
start q0
final q2
trans q0:a:q0:push:a
trans q0:b:q1:pop:a
trans q0:$:q2:pop:$
trans q1:b:q1:pop:a
trans q1:$:q2:pop:$

We can picture the DPDA as follows:



The execution of a DPDA works as follows: It starts in the start state as the "current" state. It has an input string which is assumed to be terminated with a "$" symbol. The DPDA has a stack and in the beginning the stack has a "$" symbol. The DPDA reads one symbol at a time. Depending on the current state and the symbol read, the DPDA consults the transition table to determine which state to move to, which becomes the new "current" state, and along the way performs the stack operation that is specified in the transition. The DPDA repeats this process until it has read all input symbols. At the end, if the DPDA has reached the "final" state it ACCEPTS the input otherwise it REJECTS the input. Here is a sample execution of this DPDA on input aaabbb:

   ('q0', 'aaabbb$', '$')
=> ('q0', 'aabbb$', 'a$')
=> ('q0', 'abbb$', 'aa$')
=> ('q0', 'bbb$', 'aaa$')
=> ('q1', 'bb$', 'aa$')
=> ('q1', 'b$', 'a$')
=> ('q1', '$', '$')
=> ('q2', '', '')
   ACCEPT

TO DO: Write a Python program, DPDA.py, that reads a DPDA description from a file that is specified on command line and stores the description in nested dictionaries as shown below:

  dpda_transitions = 
    {'q0': {'a': ('q0', 'push', 'a'), 
            'b': ('q1', 'pop', 'a'), 
            '$': ('q2', 'pop', '$')}, 
     'q1': {'b': ('q1', 'pop', 'a'), 
            '$': ('q2', 'pop', '$')}, 
     'q2': {}
    }

After storing the descriptions in memory, the program prompt the user for an input string and excutes the DPDA on the input and prints ACCEPT or REJECT at the end. The prompting for input must repeat until user types in n for not continuing.

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

ASCSC1PP629W1:solution raj$ more d0.pda
alphabet a b
states q0 q1 q2
start q0
final q2
trans q0:a:q0:push:a
trans q0:b:q1:pop:a
trans q0:$:q2:pop:$
trans q1:b:q1:pop:a
trans q1:$:q2:pop:$
ASCSC1PP629W1:solution raj$ python3 DPDA.py d0.pda 
enter string to test: aaabbb
('q0', 'aaabbb$', '$')
('q0', 'aabbb$', 'a$')
('q0', 'abbb$', 'aa$')
('q0', 'bbb$', 'aaa$')
('q1', 'bb$', 'aa$')
('q1', 'b$', 'a$')
('q1', '$', '$')
('q2', '', '')
ACCEPT
Do you want to try another string (y/n)?y
enter string to test: abbb
('q0', 'abbb$', '$')
('q0', 'bbb$', 'a$')
('q1', 'bb$', '$')
REJECT
Do you want to try another string (y/n)?y
enter string to test: aaaab
('q0', 'aaaab$', '$')
('q0', 'aaab$', 'a$')
('q0', 'aab$', 'aa$')
('q0', 'ab$', 'aaa$')
('q0', 'b$', 'aaaa$')
('q1', '$', 'aaa$')
REJECT
Do you want to try another string (y/n)?y
enter string to test: abab
('q0', 'abab$', '$')
('q0', 'bab$', 'a$')
('q1', 'ab$', '$')
REJECT
Do you want to try another string (y/n)?n
Bye!
ASCSC1PP629W1:solution raj$

Here is another run with a DPDA that sometimes leaves stack as is on transitions:

mirage:solution raj$ more d1.pda
alphabet a b
states q0 q1 q2
start q0
final q2
trans q0:a:q0:push:
trans q0:b:q1:pop:
trans q0:$:q2:pop:$
trans q1:a:q1:pop:
trans q1:b:q0:pop:
mirage:solution raj$ python3 DPDA.py d1.pda
enter string to test: abbaan
('q0', 'abbaaa$', '$')
('q0', 'bbaaa$', '$')
('q1', 'baaa$', '$')
('q0', 'aaa$', '$')
('q0', 'aa$', '$')
('q0', 'a$', '$')
('q0', '$', '$')
('q2', '', '')
ACCEPT
Do you want to try another string (y/n)?n
enter string to test: abbbaaa
('q0', 'abbbaaa$', '$')
('q0', 'bbbaaa$', '$')
('q1', 'bbaaa$', '$')
('q0', 'baaa$', '$')
('q1', 'aaa$', '$')
('q1', 'aa$', '$')
('q1', 'a$', '$')
('q1', '$', '$')
REJECT
Do you want to try another string (y/n)?n
Bye!
mirage:solution raj$

Modular design using functions

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

read_data() - this function reads data and returns the dictionary described earlier
run_dpda() - 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