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?

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ I suggest you keep trying. $\endgroup$ – Yuval Filmus Apr 29 '19 at 12:13
  • $\begingroup$ Have been stuck for quite some time so I don't think that will help. @YuvalFilmus $\endgroup$ – Android999 Apr 29 '19 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 '19 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 '19 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 '19 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?

|cite|improve this answer|||||
$\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.

|cite|improve this answer|||||
$\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 '19 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 '19 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 '19 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.