Pushdown Automata: Explained

Board Infinity -

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.