1
$\begingroup$

We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular.

Suppose there is a non-regular language $L$. For every finite subset $\{x_1,x_2,\ldots,x_i\}$ of elements of $L$, we can take the corresponding singleton languages and compute their union. This new language (which is a subset of $L$) should be regular. Now we do the same with rest of the language.

Finally, we must have $sL_1, sL_2,\dots, sL_n,\dots$ which are all subsets of $L$ that are finite regular languages. If we take the union of $sL_1, sL_2,\dots, sL_i$, where $i$ is finite, we again have a regular language. We do this for all languages obtained from $L$.

If we keep doing such "finite" unions of regular languages, we will eventually obtain $L$, which must be regular because we obtained it from a finite union of regular languages.

This obviously isn't right, but I don't understand why.

$\endgroup$
  • 4
    $\begingroup$ You have shown that any finite set of words is regular: true. No infinite set of words is reached by your process, leaving its regularity moot. $\endgroup$ – Thumbnail Oct 11 '19 at 17:30
  • 1
    $\begingroup$ Try to apply your procedure to the language which contains all elements and tell us after how many steps your procedure stops. $\endgroup$ – Andrej Bauer Oct 11 '19 at 19:57
7
$\begingroup$

The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

You proved that any finite languages are regular. All the languages that you generated are finite.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

You need to keep doing it an infinite number of times before you reach any infinite languages. So your proof will involve transfinite induction. As Wikipedia says:

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.

Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true. Then transfinite induction tells us that P is true for all ordinals.

Usually the proof is broken down into three cases:

  • Zero case: Prove that P(0) is true.
  • Successor case: Prove that for any successor ordinal α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β < α).
  • Limit case: Prove that for any limit ordinal λ, P(λ) follows from [P(β) for all β < λ].

It is the limit case you won't be able to prove.

| cite | improve this answer | |
$\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.