Is there a context-free but non regular language, which still meets the requirements of the regular pumping lemma?
Regular Pumping Lemma: $\exists n\in \mathbb{N}:\forall w \in L:{\mid w \mid} \geq n: \exists x,y,z\in \Sigma^*$: \begin{align} i)&w=xyz\\ ii)& {\mid y \mid} \geq 1\\ iii)& {\mid xy \mid} \leq n\\ iv)& \forall i\in \mathbb{N_0}:xy^iz\in L \end{align}

Is there any $L$ with $L\in CFL$ and $L\notin REG$ but still meets the regular pumping lemma from above?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.