1
$\begingroup$

Given the language $D = \{x^n y^n y^m \mid n,m \geq 0\}$, I have applied the pumping lemma with $k>0$, $n=k$ and $m=0$ and found a word $z = x^{k+q} y^k$ with $q>0$ that does not belong to $D$.

However, it is not sufficient to argue that the number of $x$'s and $y$'s is not equal and thus the word does not belong to $D$, as $D$ does not need an equal number of $x$'s and $y$'s.

So how would one instead argue that $z$ does not belong to $D$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The word $x^{k+q} y^k$ is not in your language for any $k$ and any $q > 0$. So I don't understand your question. $\endgroup$
    – Yuval Filmus
    Mar 6 at 6:56
  • $\begingroup$ I'm trying to understand the argument as to why your statement is true, is it that the number of $x$'s must be $\leq$ the number of $y$'s for a word to belong in the language $D$? $\endgroup$
    – Warsick
    Mar 6 at 7:15
  • 1
    $\begingroup$ Right, that’s precisely the definition of $D$. $\endgroup$
    – Yuval Filmus
    Mar 6 at 7:15

1 Answer 1

Reset to default
1
$\begingroup$

Another way to write your language is $\{x^n y^m \mid n \leq m\}$. You can see this by proving that every word in $D$ belongs to this set, and vice versa (details left to you).

This shows that if $q > 0$, then $x^{k+q} y^k \notin D$.

Improve this answer
$\endgroup$

Your Answer

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

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