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 | eRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests