1
$\begingroup$

how would you prove if this language is regular/irregular?

question given:

Decide for each of the following languages whether it is regular. If so, design a DFA/NFA for recognizing it, and if not, give a formal proof(based on the Pumping Lemma).

i) {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0 are three integers};

I have constructed a DFA which I believe proves the language is regular however, using the pumping lemma i.e. where the pumping length (p) = 4: aaaabbbbcccc, and say this is split into xyz where x = aa, y = aa and z = bbbbcccc then x(y^i)z where i = 2 -> aaaaaabbbbcccc

satisfy the conditions of the pumping lemma:

  1. for each i >= 0, x(y^i)z ∈ A
  2. |y| > 0
  3. |xy| <= p

so:

  1. when i = 2, x = aa, y = aa, z = bbbbcccc then A = aa aaaa bbbbcccc is satisfied
  2. |y| = aa so |y| = 2 which satisfies the condition
  3. x = aa + y = aa so |xy| = 4 which satisfies the condition

meaning the language is regular BUT if:

x = aaa, y = ab, z = bbbcccc

  1. when i = 2, x = aaa, y = ab, z = bbbccc then A = aaa abab bbbccc which doesn't satisfy the condition as they're not in order (a then b then c) anymore.

  2. |y| = ab so |y| = 2 which satisfies the condition.

  3. x = aaa + y = ab so |xy| = 5 which doesn't satisfy the condition.

I could be using the Pumping Lemma completely wrong I'm confused as initially (and from my DFA) I assumed this language is regular as the number of a's doesn't depend on the number of b's and the number of c's doesn't depend on the number of b's or a's etc.

basically: I think I have proven that the language is regular with a DFA but irregular with the pumping lemma and don't know how to give a definitive answer.

$\endgroup$

marked as duplicate by David Richerby, Yuval Filmus, fade2black, Evil, Kyle Jones Dec 10 '17 at 20:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You are not allowed to choose the decomposition $w = xyz$ in the pumping lemma when using it to prove that a language isn't regular. $\endgroup$ – Yuval Filmus Dec 7 '17 at 14:10
  • 1
    $\begingroup$ Your language is indeed regular. $\endgroup$ – Yuval Filmus Dec 7 '17 at 14:16
  • $\begingroup$ @DavidRicherby The question is a duplicate, but not of the question you point at: the OP already knows how to construct a DFA for their language. Rather, the OP is applying the pumping lemma in the wrong way, choosing the decomposition of the given word rather than considering all decompositions. There have been questions on this issue in the past. $\endgroup$ – Yuval Filmus Dec 7 '17 at 16:54
  • $\begingroup$ @YuvalFilmus If you can find a better duplicate, people will probably vote for it rather than the one I suggested. $\endgroup$ – David Richerby Dec 7 '17 at 16:58
2
$\begingroup$

You're using the lemma completely wrong. It states that

If language $L$ is regular, then there is $p$ such that for every string $s$ in $L$ where $|s|>p$ there is a decomposition $xyz$ with $|y|>0$ and $|xy|\le p$ for which $xy^i z \in L$ for all $i \ge 0$.

When you want to use it to prove language not to be regualr, you use contrapositive implication (making $\neg B \implies \neg A$ from $A \implies B$ ).

You get if for every $p$ there is a string $s$ with $|s| > p$ where for every decomposition $xyz$ with $|y|>0$ and $|xy| \le p$ there is a $i \ge 0$ such that $xy^i z \notin L$ then $L$ is not regular.

Now for your actual question, what you seemed to be doing is trying to prove the first implication, which would tell you nothing. It's important to note that the lemma is implication not equivalence, thus proving that a language has the pumping property does not mean it is regular. Conversely you cannot prove such languages to not be regular by pumping lemma.

If you wanted to prove that the language is not regular, you would need to make a string $s$ longer than $p$ for every $p$ from the language $L$ (for example by taking string $a^p b$ or $a^{p+1}$ or similar strings) and then you would have to make sure that there is an $i$ for all of the decompositions $xyz$ such that $xy^i z \notin L$. You can find many examples both on this site and on the Internet, but it is impossible here because the language is in fact regular.

To take your example more closely, if you wanted to prove the language to not be regular with the pumping lemma, your first mistake was chosing $p$, because you need to prove the statement for every $p$.

$\endgroup$

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