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.