Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Notes > Theory of Computation > Equivalence of Pushdown Automata with Context-Free Grammar
Equivalence of Pushdown Automata with Context-Free Grammar
| Download, print and study this document offline |
Please wait while the PDF view is loading
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
Read MoreAbout this Document
4.76/5 Rating
Apr 30, 2026 Last updated
Related Exams
Document Description: Equivalence of Pushdown Automata with Context-Free Grammar for Computer Science Engineering (CSE) 2026 is part of Theory of Computation preparation. The notes and questions for Equivalence of Pushdown Automata with Context-Free Grammar have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Equivalence of Pushdown Automata with Context-Free Grammar covers topics like and Equivalence of Pushdown Automata with Context-Free Grammar Example, for Computer Science Engineering (CSE) 2026 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Equivalence of Pushdown Automata with Context-Free Grammar.
Introduction of Equivalence of Pushdown Automata with Context-Free Grammar in English is available as part of our Theory of Computation for Computer Science Engineering (CSE) & Equivalence of Pushdown Automata with Context-Free Grammar in Hindi for Theory of Computation course. Download more important topics related with notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Equivalence of Pushdown Automata with Context-Free Grammar
Description
Equivalence of Pushdown Automata with Context of Theory of Computation covers all the important topics, helping you prepare for the Computer Science Engineering (CSE) exam on EduRev.
Information about Equivalence of Pushdown Automata with Context-Free Grammar
In this doc you can find the meaning of Equivalence of Pushdown Automata with Context-Free Grammar defined & explained in the simplest way possible. Besides explaining types of Equivalence of Pushdown Automata with Context-Free Grammar theory, EduRev gives you an ample number of questions to practice Equivalence of Pushdown Automata with Context-Free Grammar tests, examples and also practice Computer Science Engineering (CSE) tests
Related Searches
shortcuts and tricks, Previous Year Questions with Solutions, Objective type Questions, ppt, Exam, Free, past year papers, MCQs, pdf , Sample Paper, practice quizzes, study material, video lectures, mock tests for examination, Semester Notes, Summary, Important questions, Viva Questions, Extra Questions, Equivalence of Pushdown Automata with Context-Free Grammar, Equivalence of Pushdown Automata with Context-Free Grammar, Equivalence of Pushdown Automata with Context-Free Grammar;