Understanding the Pumping Lemma for Context-Free Languages
Explore the Pumping Lemma for Context-Free Languages, a fundamental concept in theoretical computer science. Learn how it applies to context-free grammars and how to use it to analyze and manipulate language structures effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Pumping Lemma for Context-Free Languages Chuck Cusack Based on Introduction to the Theory of Computation , 3rdedition, Michael Sipser
Pumping Lemma for CFLs If A is a CFL, then p such that for every s A with |s| p, s can be written as s=uvxyz satisfying 1. For each i 0, uvixyiz A, 2. |vy| > 0, and 3. |vxy| p. Condition 2 implies that v or y is non-empty. Condition 3 can be helpful at times. Notice that the substring of interest (vxy) is not necessarily at the beginning of s (unlike the pumping lemma for regular languages).
Proof: Let A be a CFL and G be a CFL generating A. Let b be the maximum number of symbols appearing on the right hand side of a rule. Let |V| be the number of variables. Let p=b|V|+1, and let s A with |s| p. Let T be a parse tree for s with the fewest nodes. T is a b-ary tree (each node b children). A b-ary tree of height h has at most bhleaves. Since each character in s is a leaf in T, the height of T is at least |V|+1.
b = max symbols on RHS of rule of G, |V| =# variables, p=b|V|+1, s A, |s| p, T is parse tree for s (has fewest nodes, height |V|+1) Proof: T has a path of length |V|+1 from the root to some leaf. The path consists of |V|+2 nodes. All but the non-leaf node are variables. Therefore one of the variables is repeated. Pick a path from with repeated variable. Pick lowest occurrence of a repeated variable. S R R y z x v u
Pumping Down S R R y z x v u
Pumping Up S R R R R y y z x x = uv2xy2z v v u
Finishing the proof Condition 2: Since T was the smallest parse tree for s, when we pumped down we didn t get the same string. Thus uxz uvxyz, so |vy| > 0 . Condition 3: We chose the lowest occurrence of R to ensure that the subtree has height at most |V|+1. Since a tree of height |V|+1 has at most b|V|+1=p leaves, |vxy| p
