0
$\begingroup$

Can $L$ be regular language if it is a union of infinitely many regular languages $L_1,L_2,L_3,...$ over the same alphabet ?

(a) can $L$ be regular ?

(b) Is $L$ always regular ?

I want to make sure my logic is right. I am saying that the answer to both question is wrong because we will need construct FA $M$ that recognizes the union of the languages but since we have infinite number of states we can't construct M with infinite number of states.

$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

$L$ certainly can be regular. Let $\Sigma$ be any finite alphabet, and let $L=\Sigma^*$; $L$ is countably infinite, so we can enumerate it as $L=\{w_n:n\in\Bbb Z^+\}$. For $n\in\Bbb Z^+$ let $L_n=\{w_n\}$; the language $L_n$ is finite, so it’s certainly regular. The language $\Sigma^*$ is also regular, and clearly $\Sigma^*=\bigcup_{n\in\Bbb Z^+}L_n$.

On the other hand, it need not be: the same reasoning shows that every infinite language is a union of infinitely many regular languages, and there are certainly infinite languages that are not regular.

$\endgroup$
4
  • 1
    $\begingroup$ Why do you say $\sum^*$ is also regular ? How do we know that $\sum^*$ is regular ? Is it a fact that given $\sum$ is any finite alphabet, $\sum^*$ is always regular ? $\endgroup$
    – Out Of Bounds
    Oct 12, 2015 at 5:00
  • 2
    $\begingroup$ @OutOfBound: Yes. The language $\Sigma^*$ is recognized by a DFA with one state: that state is an acceptor state, and all transitions obviously go from it to it, since there is no other state. $\endgroup$
    – Brian M. Scott
    Oct 12, 2015 at 5:07
  • $\begingroup$ I just have another question. Is the intersection of two infinite languages $\{\varepsilon\}$ or is it undefined ? $\endgroup$
    – Out Of Bounds
    Oct 12, 2015 at 6:13
  • 1
    $\begingroup$ @OutOfBound: The intersection depends entirely on the languages, so unless you know something about them, you cannot in general say anything about their intersection. $\endgroup$
    – Brian M. Scott
    Oct 12, 2015 at 15:06
1
$\begingroup$

Your reasoning is heuristic, but certainly not any convincing reasoning. Firstly, of course the union of infinitely many regular languages can be regular. For instance, if all the languages are the same (but you can also come up with explicit examples which are less trivial).

Think about what you actually need to do in order to show, e.g., that the second assertion is incorrect. You will have to demonstrate regular languages $L_i$ (and prove they are regular) such that the union is a language known (or prove it!) to be not regular. You must provide these details for an actual proof.

$\endgroup$
1
  • $\begingroup$ You are saying to show that the second assertion is incorrect I have to demonstrate regular languages $L_i$. But the question says infinitely many languages. How can I demonstrate infinite languages ? $\endgroup$
    – Out Of Bounds
    Oct 12, 2015 at 4:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .