1
$\begingroup$

I have this language: $L=\{x^ny^jz^k:k=j\cdot n\}$, I know I can use the pumping lemma for CFL, but I have managed to do it for $k, j, n \leq 0$, and with $k = j \cdot n$ I have not been able.

$\endgroup$
1
  • 1
    $\begingroup$ Please do not delete your question after receiving an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future. Deleting your question after receiving an answer can be considered impolite to answerers. $\endgroup$
    – D.W.
    May 29, 2021 at 7:22

1 Answer 1

1
$\begingroup$

We will replace the symbols x,y,z by a,b,c respectively , so we don't get confused when using the pumping lemma

Consider the string w = a^p b^p c^(p^2) , clearly w ∈ L , we will show that w cannot be pumped

Neither v or y can have 2 type of symbols or the order gets messed up when pumping , so both v and y must have one type of symbols ( so for ex v has only as , y has only bs )

Now if v and y don't have cs the string can't be pumped , if they have only cs the string can't be pumped too , since you can't maintain k=jn

So we know now that each of v and y must have only one type of symbol and that they must include cs but no only cs ,so y must have cs , and v must have bs (it can't have as or |vxy| > p)

The only way to pump the string now is for v = b and y = c^p , in this way whenever the string is pumped , when we add a b we add c^p , maintaining k=jn

But for this to happen |vxy| > p which is unacceptable

So w can't be pumped and thus L is not a CFL

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.