PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q3(c)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: CFL Closure, Pumping Lemma & Decision Algorithms

Question

State 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:

  1. (at least one of or is non-empty)
  2. (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.

In every case some pumped string ( or ) is not in , contradicting the Pumping Lemma. Hence, is not a context-free language.

Answer:

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.

All past exam questions for Theory of Computation