7 - Pushdown Automata

ucla | CS 181 | 2024-05-13 00:22

---

Table of Contents

• Basic Notions
• Constructing PDAs
• CFG to PDA
• Converting PDA to CFG

Basic Notions

• PDA, like NFA but with a stack feature, init empty
• Thm: a lang has a CFG iff. it has a PDA
• thus, Def: a lang is context free if it has a CFG or equiv a PDA
• every reg lang is context free
• an NFA is thus a PDA that never uses the stack
• transitions:
• basic example for nonreg langs:
  • 
  • 
• Definition of PDA
  • script P is superset

    Constructing PDAs

• Palindromes:
• twice as many as as bs:
• halves are same size but first is not the same as second half (we care abt the number of symbols and check for a difference in the halves):

CFG to PDA

• Theorem: every lang that has a CFG can be recognized by a PDA
• Pf: CFG can be expressed as
• e.g.,

  Converting PDA to CFG

• Thm: if L is recognized by a PDA, then L has a CFG
• Pf: TBA in discussion