A Pushdown Automata (PDA) is a machine that can accept Context Free grammar (CFG) just like how a Finite Automata (FA) can accept Regular Grammar (RG). PDA is implemented in compilers.
Finite automata cannot accept languages where for example: we have a string like anbn, as it cannot remember the number of a’s and b’s so it will require infinite number of states. A PDA has a storage/memory like a stack that can store such data, thus making it able to accept more complex strings and problems. A PDA has immediate access only to the symbol at the top of the stack.
There are two types of PDA
i) Deterministic Pushdown Automata (DPDA).
ii) Non Deterministic Pushdown Automata (NPDA).
A DPDA can be defined as a 7 tuple.
{ Q , ∑ , Ꞇ , ẟ , q0 , Z0 , F }
Q is the state.
∑ is the input alphabet.
Ꞇ is the stack alphabet.
ẟ is the transition table.
q0 is the start state.
Z0 is the stack top.
F is the set of all final states.
Deterministic Pushdown Automata
It is an automaton where at a single point of time we can be in only and only one state.
Example:
We want to design a PDA that can check if there are matching parentheses in a string of parentheses.
We will first have a stack with element Z0 in it as the stack top element.
Next we have to design the rules in the transition table ẟ in the form,
ẟ ( state no. Q , input element ∑ , stack top elements Ꞇ ) → ẟ ( state no it has to go to Qn , current stack top elements Ꞇ )
The idea behind checking matching parentheses is to first check for all opening brackets and pushing them onto the stack.
I) The rule for the checking the first opening bracket can be designed as follows,
ẟ ( q0 , { , Z0 ) → ẟ ( q0 , {Z0 )
This rule will check if there is an opening bracket at first when the stack is empty and push that bracket on to the stack and remain in state q0.
II) Next we will have to check for an opening bracket when an opening bracket is already at the stack top.
ẟ ( q0 , { , { ) → ẟ ( q0 , {{ )
III) The next rule will be to pop the element at stack top when there is an opening bracket on top and we encounter a closing bracket in the string.
ẟ (q0 , } , { ) → ẟ ( q0 , ^ )
Where, ^ denotes popping the element from stack.
IV) The final rule will be to check if we have reached the end of the string and if the stack is empty the stack will be empty when we reach the end f the string if the parentheses are balanced.
ẟ ( q0 , $ , Z0 ) → ẟ ( qf , Z0 )
Where qf is the final state and $ is the end of the string.
Non Deterministic Pushdown Automata
It is an automaton where at a single point of time we can be in more than one state.
Example:
We want to design a NPDA to accept strings consisting of a’s and b’s that are even palindromes.
The idea behind checking for a palindrome would be to push the elements into the stack till we reach halfway through the string, and then pop the elements. When we reach the end of the string, the stack will be empty if it is an even palindrome.
I) First, we push the first letter onto the stack. So the rules will be,
ẟ ( q0 , a , Z0 ) → ẟ ( q0 , aZ0 )
ẟ ( q0 , b , Z0 ) → ẟ ( q0 , bZ0 )
II) Next, we can come across a situation where the string has a and also the top element of stack is a , and same case with b. This can mean two things, we can either be in the first half of the string where we have to push the element on the stack, or we can be in the second half of the string where we have to pop the element from the stack. So the rules will be as follows,
ẟ ( q0 , a , a ) → ẟ ( q0 , aa ), ẟ ( q1 , ^ )
ẟ ( q0 , b , b ) → ẟ ( q0 , bb ), ẟ ( q1 , ^ )
If we are in the second half, we go to state q1, otherwise we remain in q0. These rules follow the properties of non deterministic state, where it stays in two states at a time.
III) Next, we can have a situation where the string element is a, and the stack top element is b or vice versa. In such a case we just push the element on the stack and stay in state q0.
ẟ ( q0 , a , b ) → ẟ ( q0 , ab )
ẟ ( q0 , b , a ) → ẟ ( q0 , ba )
IV) Next we concentrate on the second half of the string, i.e. when we are in state q1. We have to pop the element only if the string element and stack top element are same.
ẟ ( q1 , a , a ) → ẟ ( q1 , ^ )
ẟ ( q1 , b , b ) → ẟ ( q1 , ^ )
In both rules, we stay in q1 and pop the element from the stack.
V) In the final rule we have to check if at the end of the string whether the stack is empty, if it is empty it means that the string is an even palindrome and we move to the final state.
ẟ ( q1 , $ , Z0 ) → ẟ ( qf , Z0 )
This NPDA can also be represented as follows:
The first READ represents the state q0 i.e. the first half of the string and the next READ represents state q1 i.e. the second half of the string. When we reach the end of the string $, and we pop from the stack, if we get Z0, we accept the string as an even palindrome.
Feel free to comment below if you have any doubts related to the topic.
Recommended Articles:
Comments
Post a Comment