Understanding Pushdown Automata (PDA) in Computer Engineering
Pushdown Automata (PDA) is a powerful computational model that extends the capabilities of Finite Automata (FA) by incorporating a stack memory. PDAs can accept languages that FA cannot, making them essential in theoretical computer science. They consist of components like input tape, finite control, and stack, enabling them to process complex languages efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
UNIT IV PUSHDOWN AUTOMATA Ms. Shital Pawar Assistant Professor Computer Engineering Department Bharati Vidyapeeth s College of Engineering for Women, Pune
Pushdown Automata(PDA) Pushdown automata is a way to implement a CFG in the same way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information. Pushdown automata is simply an NFA augmented with an "external stack memory". The addition of stack is used to provide a last-in- first-out memory management capability to Pushdown automata. Pushdown automata can store an unbounded amount of information on the stack. It can access a limited amount of information on the stack. A PDA can push an element onto the top of the stack and pop off an element from the top of the stack. To read an element into the stack, the top elements must be popped off and are lost. A PDA is more powerful than FA. Any language which can be acceptable by FA can also be acceptable by PDA. PDA also accepts a class of language which even cannot be accepted by FA. Thus PDA is much more superior to FA.
Pushdown Automata(PDA) PDA Components: Input tape: The input tape is divided in many cells or symbols. The input head is read-only and may only move from left to right, one symbol at a time. Finite control: The finite control has some pointer which points the current symbol which is to be read. Stack: The stack is a structure in which we can push and remove the items from one end only. It has an infinite size. In PDA, the stack is used to store the items temporarily
Formal definition of PDA: The PDA can be defined as a collection of 7 components: Q: the finite set of states : the input set : a stack symbol which can be pushed and popped from the stack q0: the initial state Z: a start symbol which is in . F: a set of final states : mapping function which is used for moving from current state to next state.
Instantaneous Description (ID) ID is an informal notation of how a PDA computes an input string and make a decision that string is accepted or rejected. An instantaneous description is a triple (q, w, ) where: q describes the current state. w describes the remaining input. describes the stack contents, top at the left. Turnstile Notation: sign describes the turnstile notation and represents one move. * sign describes a sequence of moves. For example, (p, b, T) (q, w, ) In the above example, while taking a transition from state p to q, the input symbol 'b' is consumed, and the top of the stack 'T' is represented by a new string .
Example 1 Design a PDA for accepting a language {anb2n| n>=1}. Solution: Let us consider the string aabbbb for given language In this language, n number of a's should be followed by 2n number of b's. Hence, we will apply a very simple logic, and that is if we read single 'a', we will push two a's onto the stack. As soon as we read 'b' then for every single 'b' only one 'a' should get popped from the stack. a a a a a a a a Z0 a a Z0 a Z0 Z0 Z0 a Z0 Z0 Push a s Pop all a s
Reading all as and pushing as will be done at state q0 (q0, a, Z0) = (q0, aaZ0) Reading 1st a and pushing 2 a s onto the stack (q0, a, a) = (q0, aaa) Reading all remaining a s and pushing 2 a s for every a Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence, (q0, b, a) = (q1, ) Reading 1st b and popping topmost a from stack Thus this process of popping 'b' will be repeated unless all the symbols are read. Note that popping action occurs in state q1 only. (q1, b, a) = (q1, ) Reading all remaining b sand popping one a for every b After reading all b's, all the corresponding a's should get popped. Hence when we read as input symbol then there should be nothing in the stack. (q1, , Z0) = (q2, ) popping Z0 from stack
Now we will simulate this PDA for the input string "aaabbbbbb". (q0, aaabbbbbb, Z0) (q0, aabbbbbb, aaZ0) (q0, abbbbbb, aaaaZ0) (q0, bbbbbb, aaaaaaZ0) (q1, bbbbb, aaaaaZ0) (q1, bbbb, aaaaZ0) (q1, bbb, aaaZ0) (q1, bb, aaZ0) (q1, b, aZ0) (q1, , Z0) (q2, ) ACCEPT
Example 2 Design a PDA for accepting a language {0n1m0n| m, n>=1}. Solution: In this PDA, n number of 0's are followed by any number of 1's followed n number of 0's. Hence the logic for design of such PDA will be as follows: Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then read 0, and on each read of 0, pop one 0 from the stack.
(q0, 0, Z0) = (q0, 0Z0) (Reading 1st0 s and pushing 0 s on stack) (q0, 0, 0) = (q0, 00) (Reading all 0 s and pushing all 0 s on stack) (q0, 1, 0) = (q1, 0) (Reading fist 1 and no operation on stack) (q1, 1, 0) = (q1, 0) (Reading all remaining 1 s and no operation on stack) (q1, 0, 0) = (q1, )(Reading last sequence of 0 s and popping all 0 s) (q1, , Z0) = (q2, Z0) (ACCEPT state) This scenario can be written in the ID form as: (q0, 0011100, Z0) (q0, 011100, 0Z0) (q0, 11100, 00Z0) (q0, 1100, 00Z0) (q1, 100, 00Z0) (q1, 00, 00Z0) (q1, 0, 0Z0) (q1, , Z0) (q2, Z0) ACCEPT Now we will simulate this PDA for the input string "0011100".
PDA Acceptance A language can be accepted by Pushdown automata using two approaches: 1. Acceptance by Final State: The PDA is said to accept its input by the final state if it enters any final state in zero or more moves after reading the entire input. Let P =(Q, , , , q0, Z, F) be a PDA. The language acceptable by the final state can be defined as: L(PDA) = {w | (q0, w, Z0) * (p, , ), q F} 2. Acceptance by Empty Stack: On reading the input string from the initial configuration for some PDA, the stack of PDA gets empty. Let P =(Q, , , , q0, Z0, F) be a PDA. The language acceptable by empty stack can be defined as: N(PDA) = {w | (q0, w, Z0) * (p, , ), q Q}
Equivalence of Acceptance by Final State and Empty Stack If L = N(P1) for some PDA P1, then there is a PDA P2 such that L = L(P2). That means the language accepted by empty stack PDA will also be accepted by final state PDA. If there is a language L = L (P1) for some PDA P1 then there is a PDA P2 such that L = N(P2). That means language accepted by final state PDA is also acceptable by empty stack PDA.
Example 3 Let L= {anbncmdm | n,m >=1} fin PDA to accept the language L Solution: Acceptance by empty stack Push sequence of a s onto the stack. For every b input symbol ,pop(erase) a from stack. Push sequence of c s onto the stack. For every d input symbol ,pop(erase) C from stack.
(q0, a, Z0) =(q0, aZ0) (push first a) (q0, a, a) =(q0, aa) (push all remaining a s) (q0, b, a) =(q1, ) (erase a for first b) (q1, b, a) =(q1, ) (erase all remaining a s for remaining b s) (q1, c, Z0) =(q2, cZ0) (push first c) (q2, c, c) =(q2, cc) (push all remaining c s) (q2, d, c) =(q3, ) (erase c for first d) (q3, d, c) =(q3, ) (erase all remaining c s for remaining d s) (q3, , Z0 ) =(q3, ) (acceptance by empty stack) Transition diagram for acceptance through empty stack PDA can be written as:
Example 3 Let L= {anbncmdm | n,m >=1} fin PDA to accept the language L Solution: Acceptance by final state Push sequence of a s onto the stack. For every b input symbol ,pop(erase) a from stack. Push sequence of c s onto the stack. For every d input symbol ,pop(erase) c from stack.
(q0, a, Z0) =(q0, aZ0) (push first a) (q0, a, a) =(q0, aa) (push all remaining a s) (q0, b, a) =(q1, ) (erase a for first b) (q1, b, a) =(q1, ) (erase all remaining a s for remaining b s) (q1, c, Z0) =(q2, cZ0) (push first c) (q2, c, c) =(q2, cc) (push all remaining c s) (q2, d, c) =(q3, ) (erase c for first d) (q3, d, c) =(q3, ) (erase all remaining c s for remaining d s) (q3, , Z0) = (q4,Z0 ) (Acceptance through final state) Transition diagram for acceptance through final state PDA can be written as:
Example 4 { L= aibjck | k>=0 and i+j =k} i) Find PDA accepting through final state ii) find PDA accepting through empty stack Solution: For every input symbol a , symbol x is pushed onto the stack. For every input symbol b , symbol x is pushed onto the stack. For every input symbol c , symbol x is popped from the stack.
2. PDA accepting through empty stack: (q0, a, Z0) =(q0, xZ0) (Reading first a and pushing one x on stack) (q0, a, x) =(q0,xx) (Reading all remaining a s and pushing x on stack) (q0, b, x) =(q1,xx) (Reading first b and pushing one x on stack) (q1, b, x) =(q1, xx) (Reading all remaining b s and pushing x on stack) (q1, c, x) =(q2, ) (Reading first c and popping x from stack) (q2,c, x) =(q2, ) (Reading remaining c s and popping x from stack) (q2, , Z0) =(q2, ) (acceptance through empty stack) Transition diagram
2. PDA accepting through final state: (q0, a, Z0) =(q0, xZ0) (Reading first a and pushing one x on stack) (q0, a, x) =(q0,xx) (Reading all remaining a s and pushing x on stack) (q0, b, x) =(q1,xx) (Reading first b and pushing one x on stack) (q1, b, x) =(q0, xx) (Reading all remaining b s and pushing x on stack) (q1, c, x) =(q2, ) (Reading first c and popping x from stack) (q2,c, x) =(q2, ) (Reading remaining c s and popping x from stack) (q2, , Z0) =(q3, Z0) (Acceptance through final state) Transition Diagram
Example 5 Design PDA for accepting a language L={WcWT | W {a,b}*} Solution: WT stands for reversal of string in w. For given language set of strings will be odd length palindrome. E.g. L = {aca, bcb, aacaa, abcba, bacab, abbcbba ..} Consider a string : abbcbba b b b b b b a Z0 Z0 a a a Z0 Z0 a a Z0 Z0 q1 q2 Z0 Z0 Z0 q0 q0 q1 q0 q1 q0 q1
Steps to design PDA for given language: 1. Read a sand push a it on stack without considering topmost stack symbol. 2. Read b sand push b it on stack without considering topmost stack symbol. 3. Read c without doing any stack operation. 4. Matching a swith pop operation (To match symbol a pop symbol a ) 5. Matching b swith pop operation (To match symbol b pop symbol b ) PDA for given language is: (q0, a, ) =(q0,a) (reading a and pushing a on stack) (q0, b, ) =(q0,b) (reading b and pushing b on stack) (q0, c, ) =(q1, ) (reading c without any stack operation) (q1, a, a) =(q1, ) (matching a with a and pooping a ) (q1,b, b) =(q1, ) (matching b with b and pooping a ) (q1, , Z0) =(q2, Z0) (acceptance through final state)
Example 6 Design PDA for accepting set of all strings over{a,b} with an equal number of a s and b s. The string should be accepted by 1. Final state 2. Empty stack Solution: Stack will store excess a s over b s or excess b s over a s. Consider input as: ababbaabba a b a b b a a b b a a a b a b Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0
There should be following possible cases: 1. Stack contains topmost symbol as Z0 and input is a (q0, a, Z0 ) =(q0, aZ0) (reading symbol a and pushing a on stack) 2. Stack contains topmost symbol as Z0 and input is b (q0, b, Z0 ) =(q0, bZ0) (reading symbol b and pushing b on stack) 3. Stack contains topmost symbol a and input is a (q0, a, a) =(q0, aa) (reading a and pushing a on stack) 4. Stack contains topmost symbol b and input is b (q0, b, b) =(q0,bb) (reading b and pushing b on stack) 5. Stack contains topmost symbol a and input is b (q0, b, a) =(q0, ) (reading b and popping a from stack) 6. Stack contains topmost symbol b and input is a (q0, a, b) =(q0, ) (reading b and popping a from stack)
PDA: For acceptance through empty stack (q0, a, Z0 ) =(q0, aZ0) (q0, b, Z0 ) =(q0, bZ0) (q0, a, a) =(q0, aa) (q0, b, b) =(q0, bb) (q0, b, a) =(q0, ) (q0, a, b) =(q0, ) (q0, , Z0) =(q0, ) PDA: For acceptance through final state (q0, a, Z0 ) =(q0, aZ0) (q0, b, Z0 ) =(q0, bZ0) (q0, a, a) =(q0, aa) (q0, b, b) =(q0, bb) (q0, b, a) =(q0, ) (q0, a, b) =(q0, ) (q0, , Z0 ) =(q1, Z0) Transition Diagram Transition Diagram
Types of PDA There are two types of Pushdown Automata: 1. DPDA( Deterministic PDA) 2. NPDA(Non- Deterministic PDA) DPDA NPDA DPDA are deterministic NPDA are non deterministic Every CFL can not be recognized by DPDA Every CFL can be recognized by NPDA There is only one move in every situation There could be multiple moves under a situation Palindrome can not be accepted by DPDA. Palindrome can not be accepted by NPDA. DPDA is less powerful NPDA is more powerful
Example 1 Design PDA to check whether a given string over{a,b} ends in abb Solution: String ending in abb forms a regular language and a regular language is accepted by DFA. PDA for regular language can be constructed in two steps: 1. Design DFA. 2. Convert the DFA into PDA by accepting no-stack operation to every transition in DFA.
So, for resulting PDA M=({q0,q1,q2,q3),{a, b},{z0}, , q0,z0,{q3}) (q0, b, Z0 ) =(q0, Z0) (q0, a, Z0 ) =(q1,Z0) (q1, a, Z0 ) =(q1,Z0) (q1, b, Z0 ) =(q2,Z0) (q2, a, Z0 ) =(q1,Z0) (q2, b, Z0 ) =(q3,Z0) (q3, a, Z0 ) =(q1,Z0) (q3, b, Z0 ) =(q0,Z0)
Example 2 Design PDA to check whether a given string over{a,b} having substring abb Solution: 1. Design DFA for given regular language 2. Convert DFA into PDA
So, for resulting PDA M=({q0,q1,q2,q3),{a, b},{z0}, , q0,z0,{q3}) (q0, b, Z0 ) =(q0, Z0) (q0, a, Z0 ) =(q1,Z0) (q1, a, Z0 ) =(q1,Z0) (q1, b, Z0 ) =(q2,Z0) (q2, a, Z0 ) =(q1,Z0) (q2, b, Z0 ) =(q3,Z0) (q3, a, Z0 ) =(q3,Z0) (q3, b, Z0 ) =(q3,Z0)
Example 3 Design PDA for detection of odd palindrome over{a,b} Solution: Odd length palindrome will be of form: WaWR and WbWR E.g: aba, bab, ababa, babab, bbabb, aabaa, As palindrome is odd length middle character is either a or b and first sequence of n characters will be equal to reverse of last sequence of n characters. Following are the steps to design PDA: There is no way to find middle character in a string. So middle character will be fixed non deterministically. 1. Push first sequence of n characters on stack where n is non deterministic. 2. Match last half sequence of n characters with characters on stack by using pop operation. 3. For middle character perform no operation on stack.
Note: perform stack operations irrespective of topmost stack symbol. 1. Push first half sequence of n characters on stack. (q0, a, ) =(q0 , a) (q0, b, ) =(q0 , b) 2. For middle character perform no operation on stack. (q0, a, ) = (q1 , ) (q0, b, ) = (q1 , ) 3. For last half sequence of n characters perform matching of by pop operation. (q1, a, a) =(q1 , ) (q1, b, b) =(q1 , ) 4. Acceptance through empty stack (q1, , Z0)= (q1 , )
So, PDA is: Acceptance through empty stack (q0, a, ) = {(q0, a), (q1, )} (q0, b, ) ={(q0, b) , (q1, )} (q1, a, a) = (q1 , ) (q0, b, b) = (q1 , ) (q1, , Z0)= (q1 , ) (acceptance through empty stack) Here, Q = (q0,q1) = {a, b} = {a,b,z0} Start state = q0 Initial stack symbol = Z0
Example 4 Design PDA for detection of even palindrome over{a,b} Solution: Odd length palindrome will be of form: WWR . E.g: aa, bb, abba, baab, bbbb, aaaa, As palindrome is even length first sequence of n characters will be equal to reverse of last sequence of n characters. Following are the steps to design PDA: There is no way to find middle position in a string. So middle character will be fixed non deterministically. 1. Push first sequence of n characters on stack where n is non deterministic. 2. Match last half sequence of n characters with characters on stack by using pop operation.
1. Push first half sequence on n characters on stack First symbol can be either a or b. (q0, a, Z0 ) = (q0 , aZ0 ) (Reading first symbol a and pushing a on stack) (q0, b, Z0 ) = (q0 , bZ0 ) (Reading first symbol b and pushing b on stack) Read first half sequence of n characters and push it on stack. (q0, a, a) = (q0 , aa) (q0, b, b) = (q0 , bb) (q0, b, a) = (q0 , ba) (q0, a, b) = (q0 , ab) 2. Read last half sequence of n characters and pop first half sequence from stack. For pop operation we will do state change. In last half sequence of n characters first symbol may be either a or b (q0, a, a) = (q1 , ) (Matching first a and popping a from stack) (q0, b, b) = (q1 , ) (Matching first b and popping b from stack)
Popping remaining a s and b s for matching last half sequence a s and b s. (q1, a, a) = (q1 , ) (Matching a and popping a from stack) (q1, b, b) = (q1 , ) (Matching b and popping b from stack) Acceptance through empty stack (q1, , Z0 ) = (q1 , ) So, PDA is: (q0, a, Z0 ) = (q0 , aZ0 ) (q0, b, Z0 ) = (q0 , bZ0 ) (q0, a, a) =[ (q0 , aa) , (q1 , ) ] (q0, b, b) = [(q0 , bb) , (q1 , ) ] (q0, b, a) = (q0 , ba) (q0, a, b) = (q0 , ab) (q1, a, a) = (q1 , ) (q1, b, b) = (q1 , ) (q1, , Z0 ) = (q1 , ) Here, Q = (q0,q1) = {a, b} = {a,b,z0} Start state = q0 Initial stack symbol =Z0
Example 5 Design PDA for detection of palindrome over {a,b} Solution: Palindrome can be of even length or odd length PDA for palindrome is: (q0, a, Z0 ) = { (q0 , aZ0 ) (q1 , Z0 ) } (q0, b, Z0 ) = (q0 , bZ0 ) (q1 , Z0 ) (q0, a, a) ={ (q0 , aa) , (q1 , ) , (q1 , a) } (q0, b, b) = {(q0 , bb) , (q1 , ) , (q1 , b)} (q0, b, a) = {(q0 , ba) . (q1 , a)} (q0, a, b) = (q0 , ab) , (q1 , a)} (q1, a, a) = (q1 , ) (q1, b, b) = (q1 , ) (q1, , Z0 ) = (q1 , ) (Acceptance through empty stack)
PDA and CFG The class of language accepted by pushdown automata is exactly the class of context-free-languages. Following three classes of language are same: Context Free Language defined by CFG. Language accepted by PDA by empty stack. Language accepted by PDA by final state. So, it is possible to find PDA for CFG. It is possible to find CFG for PDA 1. 2. 3. PDA by empty stack PDA by final state CFG Equivalence of PDA and CFG
CFG to PDA Conversion The following steps are used to obtain PDA from CFG is: Step 1: Convert the given productions of CFG into GNF. Step 1: The PDA will only have one state {q}. Step 2: The initial symbol of CFG will be the initial symbol in the PDA. Step 3: For non-terminal symbol, add the following rule: (q, , A) = (q, ) Where the production rule is A Step 4: For each terminal symbols, add the following rule: (q, a, a) = (q, ) for every terminal symbol
Example 1 Convert the following grammar to a PDA that accepts the same language. S 0S1 | A A 1A0 | S | Solution: The CFG can be first simplified by eliminating unit productions: S 0S1 | 1S0 | Now we will convert this CFG to GNF: S 0SX | 1SY | X 1 Y 0 The PDA can be: (q, , S) = {(q, 0SX) | (q, 1SY) | (q, )} (q, , X) = {(q, 1)} (q, , Y) = {(q, 0)} (q, 0, 0) = {(q, )} (q, 1, 1) = {(q, )} M =({q} , {0,1} , { S, X, Y, 0,1} , , q, S, )
Example 2 Construct PDA for the given CFG, and test whether 0104 is acceptable by this PDA. S 0BB B 0S | 1S | 0 Solution: The PDA can be given as: A = {(q), (0, 1), (S, B, 0, 1), , q, S, } The production rule can be: R1: (q, , S) = {(q, 0BB)} R2: (q, , B) = {(q, 0S) | (q, 1S) | (q, 0)} R3: (q, 0, 0) = {(q, )} R4: (q, 1, 1) = {(q, )} (q, 010000, S) (q, 010000, 0BB) R1 (q, 10000, BB) (q, 10000,1SB) R2 (q, 0000, SB) R4 (q, 0000, 0BBB) R1 (q, 000, BBB) (q, 000, 0BB) R2 (q, 00, BB) R3 (q, 00, 0B) R2 (q, 0, B) R3 (q, 0, 0) R2 (q, ) ACCEPT Thus 0104is accepted by the PDA. Testing 0104i.e. 010000 against PDA: R3 R3 R3
Example 3 Draw a PDA for the CFG given below: S aSb S a | b | Solution: The PDA can be given as: P = {(q), (a, b), (S, a, b), , q,S , } The mapping function will be: R1: (q, , S) = {(q, aSb) |(q, a) | (q, b) | (q, )} R2: (q, a, a) = {(q, )} R3: (q, b, b) = {(q, )} Simulation: Consider the string aaabb (q, aaabb, S) (q, aaabb, aSb) R1 (q, aabb, Sb) (q, aabb, aSbb) (q, abb, Sbb) (q, abb, abb) (q, bb, bb) R2 (q, b, b) R3 (q, ) R3 ACCEPT R2 R1 R2 R1
Construction of CFG from PDA We can find CFG (G) for any PDA (M) such that, L(G) = L(M) We can construct an equivalent CFG for a PDA. For constructed CFG the variable will be of the form: x [p q] , where p, q Q and x . The PDA can be given by: M = { Q , , , , q0 , Z, } (Z is stack symbol) Then equivalent CFG is given by: G = (V, T, P, S) where, x V= {S, [p q] |p, q Q and X }
