2.1 Context-Free & PDA

The Chomsky Hierarchy

Grammar Rules Machine
Regular A -> a or A -> aB DFA
Context-free A -> alpha PDA
Context-sensitive alpha -> beta Turing Machine with bounded memory
Arbitrary / Turing Machine

alpha & beta means combinations of both terminal and non-terminal symbols

Ambiguity

A grammar is called ambiguous if it produces two different parse trees for the same string.

We can use such hierarchies to disambiguate grammars.

The problem of determining whether a given grammar is ambiguous is undecidable.

PDA

+stack

Transition Notation

Notation Means
a,b|cb on input a with b on top of the stack, push c (on top of b)
a,b|c on input a with b on top of the stack, pop the stack and push c
a,b| on input a with b on top of the stack, pop the stack

ID Analysis: (State, remained input, stuffs on the stack)

from top of the stack to the bottom: from left to right

PDA <=> Context-Free Grammar

Context-Free Grammar => PDA

construct a PDA that has only one state Q accepted by empty stack

  • begin:
  • for :
  • for terminal symbol a:

this PDA just use epsilon to push the rule to the stack, cancel out corresponding chars and do it over and over again until both the stack and the string are empty

PDA => Context-Free Grammar

Chomsky is a f**king genius.

construct a huge grammar between any possible states

Handout