Equivalence of Pushdown Automata with Context-Free Grammar | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


Equivalence of Pushdown
Automata with Context-Free
Grammar
Page 2


Equivalence of Pushdown
Automata with Context-Free
Grammar
Motivation
 CFG and PDA are equivalent in power: a
CFG generates a context-free language and
a PDA recognizes a context-free language.
 We show here how to convert a CFG into a
PDA that recognizes the language speci?ed
by the CFG and vice versa
 Application: this equivalence allows a CFG to
be used to specify a programming language
and the equivalent PDA to be used to
implement its compiler.
45
Page 3


Equivalence of Pushdown
Automata with Context-Free
Grammar
Motivation
 CFG and PDA are equivalent in power: a
CFG generates a context-free language and
a PDA recognizes a context-free language.
 We show here how to convert a CFG into a
PDA that recognizes the language speci?ed
by the CFG and vice versa
 Application: this equivalence allows a CFG to
be used to specify a programming language
and the equivalent PDA to be used to
implement its compiler.
45
Theorem 2.20
A language is context-free iff some pushdown
automaton recognizes it.
Note: This means that:
1. if a language
 is context-free then there is a PDA
 that
recognizes it
2. if a language
 is recognized by a PDA
  then there is a CFG
  that generates
 .
p.3/45
Page 4


Equivalence of Pushdown
Automata with Context-Free
Grammar
Motivation
 CFG and PDA are equivalent in power: a
CFG generates a context-free language and
a PDA recognizes a context-free language.
 We show here how to convert a CFG into a
PDA that recognizes the language speci?ed
by the CFG and vice versa
 Application: this equivalence allows a CFG to
be used to specify a programming language
and the equivalent PDA to be used to
implement its compiler.
45
Theorem 2.20
A language is context-free iff some pushdown
automaton recognizes it.
Note: This means that:
1. if a language
 is context-free then there is a PDA
 that
recognizes it
2. if a language
 is recognized by a PDA
  then there is a CFG
  that generates
 .
p.3/45
Lemma 2.21
If a language is context-free then some
pushdown automaton recognizes it
Proof idea:
1. Let
 be a CFL. From the de?nition we know that
 has a CFG
 ,
that generates it
2. We will show how to convert
 into a PDA
 that accepts strings
 if
 generates
 3.
 will work by determining a derivation of
 .
r – p.4/45