Proof for pumping lemma for new kind of CFL

69 Views Asked by At

I have a context-free grammar $(V,\Sigma,R,S)$ that is defined by the condition that every production in $R$ has to be on one of the following two forms:

$A\to uBv$ where $A,B\in V$ and $u,v\in\Sigma^*$

and

$A\to u$ where $A\in V$ and $u\in\Sigma^*$

The pumping lemma for languages that are produced by this grammar goes much like the pumping lemma for CFL, but the third condition is a little bit different. In the pumping lemma for CFL, the condition states that $|vxy|\leq p$, but for this new language, the condition is as follows:

$|uv|\leq p$ and $|yz|\leq p$

Can I prove the pumping lemma for this language in a similar way to the proof for pumping lemma for CFL?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, you can use the same basic idea to prove the pumping lemma for this kind of grammar. In some ways it’s easier, since the derivation tree is simpler: it has a single ‘spine’ of non-terminal symbols with terminal symbols coming off the spine on each side. The calculation of $p$ is perhaps the biggest difference: you’ll have to take into account both $|V|$ and the maximum lengths of $u$ and $v$ in productions of the type $A\to uBv$. It would be a little easier if you first proved that such a grammar can be converted to one in which every production is either of the form $A\to u$ with $A\in V$ and $u\in\Sigma^*$ or of the form $A\to \sigma B\tau$ with $A,B\in V$ and $\sigma,\tau\in\Sigma$.