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$?

$\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$ Mar 6, 2022 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, 2022 at 7:15
  • 1
    $\begingroup$ Right, that’s precisely the definition of $D$. $\endgroup$ Mar 6, 2022 at 7:15

1 Answer 1

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$.

$\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.