parsinggrammarautomata

Clarification on Regular Language pumping lemma

I've seen various proofs on proving that a language is not regular by the pumping lemma, such as something like:

However, I've only seen proofs for a non-regular language, and have never seen something that fails to be contradicted by the Pumping Lemma. How then, would the following be shown to follow the Pumping Lemma (or it to not be applicable) since they are all regular?

  1. A Language that only accepts the empty string:

enter image description here

  1. A language that accepts a*:

enter image description here

  1. A language that accepts a+:

enter image description here

How would these all be represented with the xyz part? I understand that the Pumping Lemma is only used to prove that a language is not regular, but I'm just seeing how the below items could be shown to not violate the Pumping Lemma, even though they aren't of "three sections" each?

Solution

  • The pumping lemma says that:

    Now, I assert that any finite language satisfies this constraint, without defining what it means to "be pumped". A finite language – that is, a language which only includes a finite number of sentences – has a longest sentence. Let p be one more than the length of the longest sentence in L. Now, I can confidently say that every sentence in L which at least p symbols long reveals the secret of the origins of the universe. Or that every sentence in L which is at least p symbols long is a formula for an eternal motion machine. Or anything I want. Because there are no sentences in L which are that long. So no-one can come up with a sentence in L which is at least p symbols long in order to disprove my assertion.

    Less whimsically, every sentence in L which is longer than the longest sentence in L can be pumped, whatever it means to be pumped. So the Pumping Lemma cannot disprove that a finite language L is regular, which is not surprising because we know that every finite language is regular. (Because we can write it as an alternation between each possible sentence.)

    Since the language consisting only of the empty string is finite, it is a regular language, and that fact cannot be disproved by the Pumping Lemma.

    OK, now for your other two examples. That means we actually have to look at the definition of "to be pumped". Which is as follows, continuing from the above:

    ... then ω can be pumped, which means that:

    Note that nothing in the above says that the partition x y z carries some semantic significance. Or that the division lines need to be visible to the human eye. It only says that if you crunch the three sentences together, you get ω.

    So suppose L is a* (or a+, it doesn't make any difference.) In this case, we can use p = 1 (which means that the property will also hold for any pumping greater pumping length). Suppose I have some ω ∈ L- I'm going to find x, y and z which satisfy the pumping requirements (which will demonstrate that there exists such a triple. Specifically, I'll let x be ε (the zero-length string) and y be a. So |y| is 1, which is ≥ 1. And |x y| is also 1, which is ≤ p. Then I'll let z be a|ω|−1 (that is, everything in ω after the first a). Thus, x y z is exactly the same as ω. Furthermore, x yi z is in L for any value of i, because L is simply the set of all strings consisting only of a, and adding or removing an a doesn't change that property.

    But note that the fact that I cannot disprove the regularity of a+ does not prove that it's regular. (It is regular, but I can't use the Pumping Lemma to prove that fact.) That's a basic principle of logic, which is perhaps worth underlining here, even though you said in your question that you knew that the Pumping Lemma cannot be used to prove regularity.

    Suppose I know that P implies Q, where P and Q are two statements. That, in and of itself, doesn't prove anything about the statements individually. But it's still a useful fact, because if I can prove P, then I know that Q is also true. (That's called modus ponens, because logicians love Latin.) Now, what if I can disprove P? Well, nothing. A false statement implies anything, because the false statement is never true, and thus cannot be used to disprove the implication. (This is somewhat similar to the fact that every element in an empty set satisfies any arbitrary property.) So modus ponens only works if I can prove P; disproving P provides no other useful information. But disproving Q does help. If I can disprove Q, then I know that P must be false. Because if P were true, then Q would have to be true, but it isn't. (This is called modus tollens, but you don't have to worry about that; the Latin is not on the exam.)

    And that's how the Pumping Lemma is used. The Pumping Lemma says that if a language is regular, then every sufficiently long sentence in the language can be pumped. That's a statement about languages I know to be regular, but it's of no help if I want to prove that a language is regular. However, I can turn the Lemma on its head and use modus tollens, which lets me demonstrate from a single counter-example, a sufficiently long sentence in L which cannot be pumped, that L is not regular. So that's often useful.

    But remember: A false statement implies anything, and anything implies a true statement. In other words, even if I could prove that the conditions of the Pumping Lemma hold for some language, (so Q is true), I know nothing about whether the language is regular (anything implies a true statement, so if Q is true, it's implied by regularity and also by non-regularity). And that's not just a quirk or special case. There are lots of non-regular languages which cannot be proven to be non-regular with the Pumping Lemma because all but a finite number of their sentences are pumpable.

    So I'll leave it at that, but let me add one comment. Writing that answer was a bloody pain because StackOverflow, in its historic wisdom about what is useful in an answer to a programming question, has determined that being able to write tidy and well-layed-out mathematical formulae is not necessary. Perhaps they're right; the fact that I felt compelled to use copious HTML to format this answer imperfectly doesn't prove anything, because neither the question nor the answer are about programming. (Not a single line of code was harmed in the processing of this question.)

    Questions like this, which are about computer science, logic, or mathematics, can and should be asked on http://cs.stackexchange.com or http://math.stackexchange.com; both of those sites allow the use of MathJax to easily format the mathematical content of questions and answers. So you're really doing everyone a huge favour by asking non-programming theoretical questions on sites set up to handle non-programming theoretical questions.