PPT: Context-Free Languages & Grammars Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : PPT: Context-Free Languages & Grammars Notes | EduRev

 Page 1


1
Context-Free Languages &
Grammars
(CFLs & CFGs)
Page 2


1
Context-Free Languages &
Grammars
(CFLs & CFGs)
Not all languages are regular
n So what happens to the languages
which are not regular?
n Can we still come up with a language
recognizer?
n i.e., something that will accept (or reject)
strings that belong (or do not belong) to the
language?
2
Page 3


1
Context-Free Languages &
Grammars
(CFLs & CFGs)
Not all languages are regular
n So what happens to the languages
which are not regular?
n Can we still come up with a language
recognizer?
n i.e., something that will accept (or reject)
strings that belong (or do not belong) to the
language?
2 3
Context-Free Languages
n A language class larger than the class of regular
languages
n Supports natural, recursive notation called “context-
free grammar”
n Applications:
n Parse trees, compilers
n XML
Regular
(FA/RE)
Context-
free
(PDA/CFG)
Page 4


1
Context-Free Languages &
Grammars
(CFLs & CFGs)
Not all languages are regular
n So what happens to the languages
which are not regular?
n Can we still come up with a language
recognizer?
n i.e., something that will accept (or reject)
strings that belong (or do not belong) to the
language?
2 3
Context-Free Languages
n A language class larger than the class of regular
languages
n Supports natural, recursive notation called “context-
free grammar”
n Applications:
n Parse trees, compilers
n XML
Regular
(FA/RE)
Context-
free
(PDA/CFG)
4
An Example
n A palindrome is a word that reads identical from both
ends
n E.g., madam, redivider, malayalam, 010010010
n Let L = { w  | w is a binary palindrome}
n Is L regular?
n No.
n Proof:
n Let w=0
N
10
N (assuming N to be the p/l constant)
n By Pumping lemma, w can be rewritten as xyz, such that xy
k
z is also L
(for any k =0)
n But |xy| =N and y ? e
n ==> y=0
+
n ==> xy
k
z will NOT be in L for k=0
n ==> Contradiction
Page 5


1
Context-Free Languages &
Grammars
(CFLs & CFGs)
Not all languages are regular
n So what happens to the languages
which are not regular?
n Can we still come up with a language
recognizer?
n i.e., something that will accept (or reject)
strings that belong (or do not belong) to the
language?
2 3
Context-Free Languages
n A language class larger than the class of regular
languages
n Supports natural, recursive notation called “context-
free grammar”
n Applications:
n Parse trees, compilers
n XML
Regular
(FA/RE)
Context-
free
(PDA/CFG)
4
An Example
n A palindrome is a word that reads identical from both
ends
n E.g., madam, redivider, malayalam, 010010010
n Let L = { w  | w is a binary palindrome}
n Is L regular?
n No.
n Proof:
n Let w=0
N
10
N (assuming N to be the p/l constant)
n By Pumping lemma, w can be rewritten as xyz, such that xy
k
z is also L
(for any k =0)
n But |xy| =N and y ? e
n ==> y=0
+
n ==> xy
k
z will NOT be in L for k=0
n ==> Contradiction
5
But the language of
palindromes…
is a CFL, because it supports recursive
substitution (in the form of a CFG)
n This is because we can construct a
“grammar” like this:
1. A ==> e
2. A ==> 0
3. A ==> 1
4. A ==> 0A0
5. A ==> 1A1
Terminal
Productions
Variable or non-terminal
How does this grammar work?
Same as:
A => 0A0 | 1A1 |  0 | 1 | e
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Free

,

Summary

,

PPT: Context-Free Languages & Grammars Notes | EduRev

,

Objective type Questions

,

Extra Questions

,

Viva Questions

,

Sample Paper

,

mock tests for examination

,

PPT: Context-Free Languages & Grammars Notes | EduRev

,

video lectures

,

shortcuts and tricks

,

ppt

,

Previous Year Questions with Solutions

,

Semester Notes

,

PPT: Context-Free Languages & Grammars Notes | EduRev

,

past year papers

,

study material

,

pdf

,

Important questions

,

Exam

,

MCQs

,

practice quizzes

;