3
$\begingroup$

I find it really difficult to prove non-regularity of a language using pumping lemma. I do understand that regular language is the language that can be expressed using DFA/RE. So if I can't create DFA/RE for language can I use that as proof of it's non regularity?

For example, following is an attempt to create a DFA for
0^P
where p is prime number.

Following machine accepts 2,3,5,7 which are primes. But it also accepts those which are not primes. Can it be considered as proof of non regularity of said language?

enter image description here

$\endgroup$
  • $\begingroup$ "So if I can't create DFA/RE for language can I use that as proof of it's non regularity?" -- If you can prove that you can't, yes. Just being unable to is only a proof for irregularity or lacking creativity/skill. So, have another shot (or two) at the Pumping lemma; objectively, it's not that hard. There are other methods as well. See our reference question. $\endgroup$ – Raphael Jun 9 '15 at 7:24
3
$\begingroup$

Here is how your method of proof works on the (regular) language $\{0^2,0^3,0^5,0^7\}$. I tried to construct a DFA for this language – the DFA accepting all strings, but while it accepts $0^2,0^3,0^5,0^7$, it also accepts other strings. What when wrong?

To prove that a language is not regular, we have to show that it is impossible to construct a DFA for it. Having tried and failed is not enough – maybe it's just difficult? For example, people believe that P$\neq$NP, but so far we haven't been able to prove this. Does this show that P=NP?

How, then, can we show that a language is not regular? One way is to construct the "canonical" DFA, and this leads to the Myhill–Nerode criterion (look it up). This method is complete in the sense that if a language is not regular, then you can prove this using this method.

Another technique is the pumping lemma, which is popular for historical reasons. The pumping lemma is not complete: there are irregular languages which satisfy the conditions of the pumping lemma, and so the pumping lemma cannot be used to prove that they are not regular.

There are other techniques as well, for example using closure properties of regular languages, or using structure theorems. Your specific language is a unary language (a language over an alphabet with size 1), and we have a complete structure theorem for these languages, which can be used to show that your language is not regular.

$\endgroup$

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.