A pushdown automaton is a process that includes a context-free grammar in a same way we design DFA for a regular grammar. A DFA includes a finite amount of information, but a PDA includes an infinite amount of information.
Generally a pushdown automaton is −
"Finite state machine" + "a stack"
A pushdown automaton includes three components −
The stack head scans the top symbol of the stack.
A stack performs two operations −
While,A PDA may not read an input symbol, as it has to read the top of the stack in every transition.
A PDA is generally explained as a 7-tuple (Q, ∑, S, δ, q0, I, F) −
Below mentioned diagram explains a transition in a PDA from a state q1 to state q2, labeled as a,b → c −
This indicates at state q1, if we meet an input string ‘a’ and top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2.
The instantaneous description (ID) of a PDA is marked as a triplet (q, w, s) where
The "turnstile" notation is meant to be connect different pairs of ID's which represents more than two moves of a PDA. This process of transition is expressed with the turnstile symbol "⊢".
Let’s consider a PDA (Q, ∑, S, δ, q0, I, F). Following transition is mathematically represented by the following turnstile notation –
This is applicable where the transition from state p to state q, the input symbol ‘a’ is consumed, and the top of the stack ‘T’is replaced by a new string ‘α’.
Note − If we want zero or more moves of a PDA, we have to use the symbol (⊢*) for it.
Automata Theory Tutorial
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.