0
$\begingroup$

Deciding if the infinite union of a set of regular languages is regular is undecidable.

By closure property of regular languages, regular language is not closed under infinite union so is the above problem undecidable?

$\endgroup$
  • 2
    $\begingroup$ That really depends on how you encode an infinite union of languages. How would you represent it? $\endgroup$ – Shaull Dec 2 '17 at 18:38
  • $\begingroup$ You can assume however you want and answer. I don't know how will answer vary based on encoding. $\endgroup$ – Sagar P Dec 2 '17 at 19:58
  • 1
    $\begingroup$ OK, but is there any encoding at all? Suppose your question is, "If you gave me an infinite amount of gold, would I be able to buy the whole world?" @Shaull says, "Well, even supposing I had an infinite amount of god, how would I be able to transport that to you?" If you can't propose some way of doing that, your question is completely moot, since you'll never have the infinite amount of gold. $\endgroup$ – David Richerby Dec 2 '17 at 20:54
3
$\begingroup$

The question is not well defined, so the answer can be either decidable or undecidable.

Here are two extreme (and naive) examples of this issue.

  1. Suppose your input consists of a single DFA $A$ (i.e. we input a single regular language), and the question is whether $\bigcup_{i\in \mathbb{N}} L(A)$ is regular. That is, we take an infinite union of the same language. This is clearly decidable, as the answer is always "yes" (the language is always regular).

  2. Suppose your input is a Turing Machine $M$ that takes as input a natural number $n$ (in binary) and either halts on $n$ or doesn't. We define our regular languages $L_n$ for every $n\in \mathbb{N}$ such that $L_n$ contains a single word, which is the binary encoding of $n$. Then, the question at hand is equivalent to asking of the language of $M$ is regular, which is famously undecidable (in fact, it's neither in $RE$ nor in $coRE$).

Thus, there is clearly something missing in the question.

$\endgroup$
  • $\begingroup$ What in case of language like {ab} union {aabb} union {aaabbb} and so on.. It is of form {a^n b^n} which is non regular. $\endgroup$ – Sagar P Dec 3 '17 at 10:10
  • $\begingroup$ @SagarP - Are you claiming that sometimes you'll get a regular language, and sometimes you won't? Indeed. If this wasn't the case, then the problem would have been decidable... $\endgroup$ – Shaull Dec 3 '17 at 10:39
  • $\begingroup$ I want to know in which of the above cases in your answer will my above language fit in . Because we can't have a single DFA for union of the above language. $\endgroup$ – Sagar P Dec 3 '17 at 12:00
  • 1
    $\begingroup$ Again, the problem is how you specify the input. In my example (2), the TM will halt on words of the form a^nb^n. But that's not the point, because in (2) the problem becomes undecidable... $\endgroup$ – Shaull Dec 3 '17 at 12:24
4
$\begingroup$

Since every language is a countable union of regular languages, you're basically asking whether one can decide whether a given language is regular. Thus, for any reasonable representation, this task will be undecidable.

Consider the following representation of your problem, say a machine $M$ represents an infinite series of regular expressions if given input $i$, $M$ produces a regular expression $r^M_i$. You now ask whether the following language is decidable:

$L=\left\{\langle M\rangle \Big| \text{$\bigcup\limits_{i}L\left(r_i^M\right)$ is regular}\right\}$

If $M$ does not represent a series of regular expressions, i.e. on some input $i$, $M(i)$ is not a valid regular expression, then $\langle M\rangle\notin L$. $L$ is undecidable, since you can reduce the language $L_R=\{\langle M\rangle | \text{$L(M)$ is regular}\}$ to it ($L_R$ is trivially undecidable by Rice theorem). Your reduction will, given $M$, generate a machine $M'$ which on input $i$ will simulate $M$ on all inputs of length $\le i$ for $i$ steps, and according to the result, will generate a regular expression which corresponds to the union of all words that were accepted during this simulation. Clearly $\bigcup\limits_{i}L\left(r_i^{M'}\right)=L(M)$, and the validity of the reduction immediately follows.

$\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.