Infinite union of regular language - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T13:37:51Z https://cs.stackexchange.com/feeds/question/84813 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/84813 0 Infinite union of regular language Sagar P https://cs.stackexchange.com/users/79162 2017-12-02T18:36:20Z 2017-12-02T20:32:59Z <p>Deciding if the infinite union of a set of regular languages is regular is undecidable.</p> <p>By closure property of regular languages, regular language is not closed under infinite union so is the above problem undecidable?</p> https://cs.stackexchange.com/questions/84813/-/84819#84819 3 Answer by Shaull for Infinite union of regular language Shaull https://cs.stackexchange.com/users/6890 2017-12-02T20:24:32Z 2017-12-02T20:24:32Z <p>The question is not well defined, so the answer can be either decidable or undecidable.</p> <p>Here are two extreme (and naive) examples of this issue.</p> <ol> <li><p>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).</p></li> <li><p>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$).</p></li> </ol> <p>Thus, there is clearly something missing in the question.</p> https://cs.stackexchange.com/questions/84813/-/84821#84821 4 Answer by Ariel for Infinite union of regular language Ariel https://cs.stackexchange.com/users/27055 2017-12-02T20:32:59Z 2017-12-02T20:32:59Z <p>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.</p> <p>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:</p> <p>$L=\left\{\langle M\rangle \Big| \text{$\bigcup\limits_{i}L\left(r_i^M\right)$is regular}\right\}$</p> <p>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.</p>