Equivalence of Pushdown Automata with Context-Free Grammar

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

 Download, print and study this document offline
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

## Theory of Computation

18 videos|56 docs|44 tests

## Theory of Computation

18 videos|56 docs|44 tests

### Up next

 Explore Courses for Computer Science Engineering (CSE) exam

### Top Courses for Computer Science Engineering (CSE)

Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;