Pushdown Automata: Explained
Introduction
A context free grammar (CFG) can be implemented using push down automata (PDA), which is akin to how deterministic finite automata (DFA) are created for regular grammars.
A PDA can store unlimited amounts of information but a DFA can only store a finite quantity.
A PDA basically includes the following:
"Stack plus a finite state machine"
The three parts of a PDA are as follows:
- A cassette for input.
- A control system.
- An infinitely long stack.
A PDA might or might not be able to read input symbols, but every transaction requires it to read the top of the stack.
7-tuples are the formal definition of a PDA
(Q, ∑,S, δ,q0,I,F)
- Q is a finite number of states.
- ∑ is the input alphabet.
- S is a stack symbol.
- δ is the transition function: QX(∑U{e}) XSXQ
- q0 is the initial state (q0 belongs to Q).
- I is the initial state top symbol.
- F is a set of accepting states (F belongs to Q).
Diagram
The diagram depicts a PDA transition from state q1 to state q2, which is denoted by the symbols a,b->c.
If an input string of 'a' is found in state q1, and the top symbol of the stack is 'b,' we pop 'b,' push 'c,' and go to state q2.