2
$\begingroup$

I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it.

The alphabet is:

$$ \Sigma = \{c, d\} $$

The language is:

$$ A = \{z \in \Sigma^* \mid c(z) > d(z)\} , \text{where $c(w)$ and $d(w)$ means occurrences of $c$ or $d\in z$ }$$

I tried to define a string like so:

Pumping length = P

$$ s = c^{(P+1)}d^P $$

Here is how I tried to solve it:

If we select P = 5. Then s = ccccccddddd and split it in 3 parts. Where x = ccccccd, y = ddd and z = d. (Is that even allowed though as |xy| <= P, but now |xy|=10 and 10>5). If I then do y^2. Then I get s = ccccccdddddddd, so now d>c which proves the string is not in the language. Does this then prove that the language is not regular?

$\endgroup$
  • 1
    $\begingroup$ I suggest you keep trying. $\endgroup$ – Yuval Filmus Apr 29 at 12:13
  • $\begingroup$ Have been stuck for quite some time so I don't think that will help. @YuvalFilmus $\endgroup$ – Android999 Apr 29 at 12:24
  • $\begingroup$ You won’t understand the material if other people solve all exercises for you. This is a relatively simple application of the pumping lemma, so it’s there to help you practice the basics. $\endgroup$ – Yuval Filmus Apr 29 at 12:39
  • $\begingroup$ Yes I do know this is probably basics, but I would like an answer that I then could look back on when solving the other exercises in the future. @YuvalFilmus $\endgroup$ – Android999 Apr 29 at 12:47
  • 1
    $\begingroup$ I seems you are on the right track, but try to switch the order of $c$'s and $d$'s in your string, so $s = d^p c^{p+1}$. $\endgroup$ – AcId Apr 29 at 12:51
2
$\begingroup$

You need to show that with that arbitrary pumping length $P$, for any partition $c^{(P+1)}d^P = xyz$ such that $|y|>0$ and $|xy|\leq P$, there is some $i$ such that $xy^iz \not\in A$.

Since for any partition we require that $|xy|\leq P$, then $x$ and $y$ necessarily consist only of $c$'s. Also, you know that $|y| >0$ (it's also a requirement). Can you find an $i\in\mathbb{N}$ such that the amount of $c$'s in $xy^iz$ is less than or equal to the amount of $d$'s?

$\endgroup$
1
$\begingroup$

You need to pick a string that's in the language (i.e., has fewer $d$s than $c$s) but, when pumped, creates strings that are not in the language (more $d$s than $c$s). Think about how you can achieve that.

$\endgroup$
  • $\begingroup$ Okay I tried to solve it. Do you think the solution I did above is valid or am I missing something? $\endgroup$ – Android999 Apr 29 at 13:44
  • $\begingroup$ @Android999 you can't claim to know what $p$ is, nor can you define $x$, $y$, or $z$. The answer is given here. Carefully review the laws of the lemma and make sure you understand this answer $\endgroup$ – lox Apr 29 at 14:05
  • $\begingroup$ @Android999 That's not quite right, for the reasons that lox points out and because we require $|xy|\leq P$. But the language is strings of $c$s and $d$s in any order, which mean you can choose a similar $s$ which makes your life easier. Or you could choose a different number of repetitions for $y$, which can also be made to work. $\endgroup$ – David Richerby Apr 29 at 14:11

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.