How can I prove whether irregular languages are infinite? I thought about proving it by the definition of regular language but got stuck.

| cite | improve this question | | | | |
  • 3
    $\begingroup$ Have you tried proving the contra-positive: that every finite language is regular? Where did you get stuck? $\endgroup$ – Shaull Jan 17 '16 at 10:20
  • $\begingroup$ yes, i have, but what next? i got stuck after proving that it doesnt have finite automata (because it is not regular), what should I do now? $\endgroup$ – Adi Ml Jan 17 '16 at 10:23
  • $\begingroup$ What does not have a finite automata? That's does not seem to be a required step in either a direct proof nor one following @Shaull's (very apt) hint. $\endgroup$ – Raphael Jan 17 '16 at 10:40
  • $\begingroup$ i didnt found finite automata to the irregular language $\endgroup$ – Adi Ml Jan 17 '16 at 10:49
  • $\begingroup$ If you've proved that every finite language does have a finite automaton, then where are you stuck? Can you see that the two claims are equivalent? I suggest you try to write down exactly what you have, and we'll take it from there. $\endgroup$ – Shaull Jan 17 '16 at 10:54

I suppose that by "irregular languages" you mean non-regular languages, that is languages that are not regular. An intuitive classification between regular and non-regular languages is based on their recognizers. In case of regular languages, Finite State Automata are enough, while for non-regular languages you need more powerful automata.

A language is regular if you can build a FSA for it. Thus, given that you can always build an FSA for a language with a finite number of strings (via the Prefix Tree Acceptor, for example), than every language with a finite number of strings is regular.

If a language has an infinite number of strings, it can be regular or not, it depends (you could use the pumping lemma or other approaches to demonstrate if the language is not regular: take a look here: How to prove that a language is not regular?); on the other hand, no language with a finite number of strings is non-regular. Hence, non-regular languages are composed of an infinite number of strings.

I hope this can help you.

| cite | improve this answer | | | | |
  • $\begingroup$ but my language is some general language which i define as non regular, so, how can i prove that it has infinite length? $\endgroup$ – Adi Ml Jan 17 '16 at 12:36
  • 1
    $\begingroup$ @AdiMl Restating the question in response to an answer is a clear sign that you are missing something fundamental. It seems to me that you don't understand the concept of proof by contrapositive. You may want to work through a textbook on basic logic and proof technique, e.g. the (free) Book of Proof. $\endgroup$ – Raphael Jan 17 '16 at 13:33

Here's a proof in more or less complete detail. You want to show that non-regular languages are infinite. In more formal terms, this statement is

If $L$ is a non-regular language, then $L$ is infinite.

Let's define two predicates, $P=\text{"$L$ is not regular"}$ and $Q=\text{"$L$ is not finite"}$. Then your statement is the same as asserting $P\Rightarrow Q$, and you want to show that this implication is true (for any language L$).

Fact 1. The expression $P\Rightarrow Q$ is logically equivalent to $\lnot Q\Rightarrow \lnot P$ (called the contrapositive). In other words, if we can prove that $\lnot Q\Rightarrow \lnot P$ is true, then $P\Rightarrow Q$ must also be true.

Using this equivalence, we can show that the highlighted sentence above is true by showing that

If $L$ is finite, then $L$ is regular.

is true.

To prove this, you can use two facts:

Fact 2. If a language consists of a single string, $w$, then it is regular. This is almost immediately obvious: just make a finite automaton that accepts $w$ and nothing else.

Fact 3. The union of two regular languages is regular. This is a result that you should have seen.

From these two facts, you can conclude (by induction),

Fact 4. Any language consisting of a finite number of strings is regular.

Note that this is exactly the second highlighted statement above, so, since it is logically equivalent to the first statement above, that statement must be true: Every non-regular language is infinite. That completes the proof.

| cite | improve this answer | | | | |
  • $\begingroup$ thats a lot!!!! $\endgroup$ – Adi Ml Jan 18 '16 at 14:40

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