PPT: Context-Free Languages & Grammars | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 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