Push Down Automata (PDA)

Introduction

Definition

• Pushdown automata are an abstract computational model that uses a stack to recognize context-free languages.
• A Push-Down Automaton is a finite automaton with a stack that allows push and pop operations to store and retrieve symbols.

Characteristics

• PDA is more powerful than a Finite Automaton because it has an additional memory structure called a stack, which helps in push and pop operations of symbols.
• It is more powerful than finite automata but less powerful than a Turing machine.
• PDA is mainly used to recognize context-free languages (CFLs) such as balanced parentheses and expressions.

Structure/Components of PDA

• A PDA consists of:-
  • Finite set of states (Q)
  • Input alphabet (Σ)
  • Stack alphabet (Γ)
  • Transition function (δ)
  • Start state (q₀)
  • Initial stack symbol (Z₀)
  • Set of final states (F)

Types of PDA

• Deterministic PDA (DPDA)
  • Only one possible move for each input.
• Non-Deterministic PDA (NPDA)
  • It has multiple possible moves.
  • It is more powerful than DPDA.

Advantages of PDA

• PDA handles the concepts of recursion and nesting.
• PDA is more powerful than FA.

Limitations of PDA

• It cannot recognize all languages.
• It cannot handle $a^n b^n c^n$

Use/Applications

• The concept of PDA is used in syntax analysis in compilers.
• It helps in parsing programming languages.
• It is used in expression evaluation.
• It helps in matching/checking balanced parentheses.
• It also helps in XML/HTML parsing.
• Syntax analysis in compilers