Past exam question: 2081 Chaitra (Regular), Q3(c)
Open in the Padhaiko appState pumping lemma for context free language and show that is not CFL.
Solution
Pumping Lemma for Context-Free Languages: The Pumping Lemma for CFLs states that if is a context-free language, there exists a pumping length such that any string with can be written as satisfying:
- (at least one of or is non-empty)
- (the pumped substring has length at most )
Proof that L = {ww} is Not Context-Free: Assume for contradiction that is a context-free language. Let be its pumping length.
Choose string with . Clearly .
According to the lemma, with and .
Because , the substring cannot span both the first half of () and the entire second half (): Let , so . Every string of has even length, so if is odd the pumped string (length ) is already outside . Assume is even below.
- Case 1: lies entirely within the first half . Pump up (). The string has length , so its midpoint moves places to the right of the old one, with . The extra symbols were added in front of the old midpoint, so the new second half begins symbols before the old midpoint, that is, inside the first block . So the second half starts with , while the first half still starts with . The halves differ: .
- Case 2: lies entirely within the second half . Pump up (). Now the extra symbols lie after the old midpoint, so the new midpoint moves places right, into the second block (as ). The new first half therefore ends with , while the new second half ends with the final , i.e. with . The halves differ: .
- Case 3: straddles the midpoint (it meets the first block and the second block; since it cannot reach the outer blocks). Pump down (): the result is with . Its length is , so each half has length . The first half begins with . The second half is the last symbols: it ends with the final block , so only its first symbols come before that block. Hence position of the second half is a , while the same position of the first half is a . The halves differ: .
In every case some pumped string ( or ) is not in , contradicting the Pumping Lemma. Hence, is not a context-free language.
Assuming is a CFL with pumping length , selecting ensures that substring () cannot alter both identical halves symmetrically. Pumping up () when lies in one half, or down () when it straddles the middle, always yields a string that is not of the form , proving is not context-free.