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 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$ Mar 6 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, privacy policy and cookie policy

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