1
$\begingroup$

So I'm trying to practice (and learn, clearly) use of the Pumping Lemma, and this is my current equation. It's clearly regular- it can be simplified:

$a^{2+n}a^{n} = a^{2+2n}$ and from there it's fairly easy to derive the regular language $aa(aa)*$

However, I'm trying to explicitly solve this through the Pumping Lemma- but clearly doing something wrong. This is my process (assuming language $A$, string $s$ in $A$, pumping length $p$):

First take $s = aaaa$ for $n = 1$ (simple case).

Take $p = 2$, and so $xy$ must equal $aa$ to fit $|xy| \leq p$ and $|y| \gt 0$ , giving $x = a, y = a, z = aa$.

Finally insert into the equation $xy^{i}z \in A$ with a trivial value of $i \geq 1$ - $xy^{2}z$. This gives a result of $aaaaa$.

And that's the problem. $aaaaa$ is not a member of the language $a^{2+n}a^{n}$. Is there a step I'm missing here or a wrong assumption?

Thanks. And apologies for yet another pumping-lemma question.

$\endgroup$
5
$\begingroup$

Noooooo!

Usage of the pumping lemma to prove regularity is remarkably rare, and certainly won't happen with a direct application.

Let's review the formal statement, with particular emphasis on the quantifiers:

$$\forall \ L \subseteq \Sigma^* ( \ L \ \text{is regular} \Rightarrow \exists \ p \ge 1 \ \ \forall \ w \dots \ \ \exists \ x, y, z \dots \ \ \forall \ i \dots \ )$$

Two notable observations are that being regular is part of the hypotheses and that nothing is said about the converse, which is in fact false (a number of classical counterexamples can be found in literature).

In other words, even if you managed to somehow prove the $\exists \forall \exists \forall$ block, it still wouldn't say anything about the regularity of $L$. The way the pumping lemma is normally used is in its contrapositive form. You may recall from basic logic that $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$. Using that principle, we can derive the following logical consequence:

$$\forall \ L \subseteq \Sigma^* ( \ \forall \ p \ge 1 \ \ \exists \ w \dots \ \ \forall \ x, y, z \dots \ \ \exists \ i \dots \Rightarrow L \ \text{is }\textbf{not }\text{regular} \ )$$

Notice how this is a tool to prove non-regularity, and that, even there, nothing can be said about the converse.

I'm afraid your attempt of proof is just entirely misguided.

$\endgroup$
  • $\begingroup$ D'oh! I've just had a look back over some lecture notes and found that much has been said. That said, we've only been told that regular languages can be "[checked] using a DFA or NFA" or trivially in cases such as above- is there a better way? Thanks again $\endgroup$ – Overt_Agent Jan 18 '17 at 19:05
  • $\begingroup$ @Overt_Agent You're welcome! Proving things is inherently non-algorithmic, there is no one way. Generally, to prove regularity you do one of the following: (a) show a/an ($\epsilon$)-[D|N]FA, (b) write a regular expression for the language, or (c) use the closure properties of the set of regular languages. Generally, regular languages are nice enough that one of the above will single-handedly complete the proof. If that's not the case, you'll have to come up with an idea of your own. $\endgroup$ – quicksort Jan 18 '17 at 19:21

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.