3
$\begingroup$

Prove or disprove: There exists an infinite set of different irregular languages such that their union is a regular language.

My intuition led me to try to disprove, since if I had a set that is built by union of infinite different irregular languages, the automat that I need to build that accepts that set should accept every set that builds that union, and so I think that that automat doesn't exist.

My Attempt to Disprove:

Let's denote the set $L$ as an infinite union of irregular languages.
Assume by contradiction that $L$ is regular, that means there exists an automat $A$ such that $L(A)=L$.
Since $L$ is an infinite union of irregular languages then we can write: $$L=\bigcup_{i\in \mathbb{N}}L_i$$ Where $L_i$ is irregular for each $i\in\mathbb{N}$.

Let's check if there exists $A$ such that $L \subseteq L(A)$ first. Let $x\in L=\bigcup_{i\in \mathbb{N}}L_i$, that means $x\in L_1$ or $x\in L_2$ or ... $x\in L_i$.
Without loss of generality, let's say $x\in L_i$, but $L_i$ is an irregular language, which by definition means that there doesn't exist an automat $B$ such that $L(B)=L_i$, so I can infer that there is no automat $A$ such that $x\in L(A)$ which means $L\nsubseteq L(A)$ so $L\ne L(A)$. which is a contradiction.

Possible mistakes I thought of and struggling to approve:

  1. If there isn't an automat $B$ such that $L(B)=L_i$. then if $x\in L_i$, then can I really infer that $x\notin L(B)$? what if $x$ is in both of them even if they aren't equivalent?
  2. I'm not sure that writing $L$ as I did is the correct way of expressing what's written in the question.
$\endgroup$
5
  • 3
    $\begingroup$ Without picking through the proof, I can tell you that the result is false. Take, for example, for any $n \in \Bbb{Z}$, the irregular (but context-free) language $L_n = \{a^i b^j : i - j = n\}$. What is the union of this family of languages, over $n \in \Bbb{Z}$? $\endgroup$ Feb 15, 2022 at 0:44
  • $\begingroup$ @TheoBendit I can guess that if we take an infinite union we will be able to reach every $i,j\in \mathbb{Z}$ so $L=\{a^ib^j : i,j\in \mathbb{Z} \}$, which can be built easily by an automat that accepts everything... Thanks for the help, but I would like to ask for the intuition you had that made you reach this example. My knowledge is still at DFA and regular languages. The only irregular language I saw until now is $L=\{a^ib^i : i \ge 0 \}$. Does it just come by with more experience or would you say I could've reached an answer based on my knowledge? Would appreciate any extra explanation.. $\endgroup$
    – Pwaol
    Feb 15, 2022 at 0:56
  • 2
    $\begingroup$ It doesn't union to everything. For example, $aba$ will not be in any of the $L_n$s. What it gives you is the regular expression $a^* b^*$, i.e. the language where all the $a$s come before all the $b$s. As for how I got this, yes it is more experience. If you have only seen the one irregular language, I don't know how you're supposed to know infinitely many which you could union. It strikes me as an unfair question. If you understand *why* $a^ib^i$ is not regular, then you might be able to reasonably guess the $L_n$s are not regular, but that would be asking a lot. $\endgroup$ Feb 15, 2022 at 1:05
  • 2
    $\begingroup$ If you want to prove the $L_n$s are not regular, you should use pumping lemma, if you know it. Unfortunately, using it properly cannot be done in a comment. $\endgroup$ Feb 15, 2022 at 1:06
  • $\begingroup$ @TheoBendit Thanks alot, I can see the regular expressions is in the next module in my book and the pumping lemma soon after, seems like I am solving these at the wrong time, I want to keep the question so I can see where my proof "falls apart", because I'm not sure which parts are correct steps and which are the wrong ones, I think it's important to know where my mistakes are. Appreciate your help alot. $\endgroup$
    – Pwaol
    Feb 15, 2022 at 1:18

2 Answers 2

2
$\begingroup$

Well, since no one else answered, I might as well.

Let’s check if there exists $A$ such that $L \subseteq L(A)$.

There is. There always is. The full language of all strings is regular. It’s accepted by an automaton with one state, both initial and terminal, and a looping arrow for every symbol in the alphabet.

…which by definition means that there doesn't exist an automat $B$ such that $L(B)=L_i$, so I can infer that there is no automat $A$ such that $x\in L(A)$ which means…

Here’s the false implication; your concern number 1 was well-founded. Any single string can be accepted by an automaton. Naturally, there’s the automaton that accepts everything as outlined above. But also, any language containing a single word (any word you like) is regular.

So, for example, $aabb \in \{a^nb^n : n \in \Bbb{N}\}$, but it’s also accepted by many automata. For example, consider an automaton with $5$ states, $1, 2, 3, 4, 5$, where $1$ is initial and $5$ is terminal. Let an $a$ arrow connect $1$ to $2$ and $2$ to $3$, while a $b$ arrow connect $3$ to $4$ and $4$ to $5$. Such an automaton accepts $aabb$ and only $aabb$.

You might be able to see how this extends to any word: make one state for every symbol in the word, plus an extra terminal one, and let the arrows from one state to the next be the next symbol in the word. So, indeed, any language consisting of a single word is regular.

What I’m saying is, you cannot determine by looking at a single word in a language (or even finitely many words) if a language is regular or not.


Let me expand the comments under the question, which provide the actual solution to this exercise:

You are, as you said in the comments, familiar with $\{a^n b^n : n \in \Bbb{N}\}$ (or alternatively, $\{a^i b^j : i = j\}$) being irregular. Let’s call it $L_0$. For $n \in \Bbb{Z}$, let $$L_n = \{a^i b^j : i - j = n\}.$$ I claim that $L_n$ is irregular.

The standard way to do this kind of thing is using pumping lemma, and indeed this is the way $L_0$ is typically proven to be irregular. However, we can also prove this using operations known to preserve regular languages:

Suppose $M_1$ and $M_2$ are two regular languages. Then $M_1 \cup M_2$ is regular.

Sketch proof: It’s easier if you know about non-deterministic automata, and how they only accept regular languages. All you do is merge the initial states of the two automata that accept $M_1$ and $M_2$, and keep the arrows coming from it to the two different automata. Because both automata could have an arrow with the same label coming from their initial state, this could make the automaton non-deterministic.

Using the fact that languages consisting of a single word are regular, and the empty language is regular, this means that finite languages are regular too.

Suppose $M_1$ and $M_2$ are regular. Then $M_1M_2 = \{w_1w_2 : w_1 \in M_1, w_2 \in M_2\}$ is regular.

Sketch proof: If $A_1$ and $A_2$ are automata for $M_1$ and $M_2$, turn each accepting state of $M_1$ into the initial state of a copy of $A_2$, so that once $A_1$ accepts the first part of the word, then $A_2$ can judge the remainder of the word. Once again, this may turn out non-deterministic, but this isn’t a problem.

So, using these results, note that, for $n \in \Bbb{N}$, the singleton languages $\{a^n\}$ and $\{b^n\}$ (note: $n$ is a fixed natural number, and the sets have only one element) are regular. So, if I assume that $L_n$ or $L_{-n}$ is regular for some $n \in \Bbb{N}$ (for the sake of contradiction), then I may conclude that one of the concatenations $L_n\{b^n\}$ or $\{a^n\}L_{-n}$ are regular. Note that $$L_n\{b^n\} = \{a^n\}L_{-n} = \{a^k b^k : k \ge n\},$$ so in either case, $\{a^k b^k : k \ge n\}$ is regular.

Now, note that $$L_0 = \{a^k b^k : k \in \Bbb{N}\} = \{a^k b^k : k \ge n\} \cup \{\varepsilon, ab, a^2b^2, a^3b^3, \ldots, a^{n-1}b^{n-1}\},$$ which is a finite union of a regular language with a finite language (which is therefore regular), so in total, we get $L_0$ is regular. This contradicts your knowledge about $L_0$ being an irregular language. Thus, my assumption that $L_n$ or $L_{-n}$ is regular for some $n \in \Bbb{N}$ is false. So, $L_n$ is irregular for all $n \in \Bbb{Z}$.

(Of course, if you’re attempting this exercise at the right time in your study, you won’t have to do this much proof!)

We have $$\bigcup_{n \in \Bbb{Z}} L_n = \{a^ib^j : i,j \in \Bbb{N}\}.$$ Why? Certainly any $a^ib^j \in L_n$, for any given $n \in \Bbb{Z}$, takes the correct form, so we definitely have $\subseteq$. On the other hand, given $a^ib^j$ in the right hand side, $i - j \in \Bbb{Z}$, so let it be $n$. Then $a^i b^j \in L_n$, giving us $\supseteq$.

The language on the right is regular. It is accepted by an automaton with two states, both accepting, the initial one having a looped $a$ arrow, plus a $b$ arrow to the next state. The next state also has a looping $b$ arrow. So, we have our counterexample.

$\endgroup$
1
  • $\begingroup$ Thanks SO much for this great answer, I liked the way you proved that $L_n$ is irregular, I've spent long time understanding why $L_n\{b^n\}=\{a^n\}L_{-n}=\{a^kb^k : k\ge n \}$. The way I convinced myself is by doing this: $L_n\{b^n\}=\{a^ib^{j+n}: i-j=n \}$ and if we set $i=j+n=k$, then we reach the result. But I can see this trick being generalized: for example $\{a^ib^j: i+j=n\}$, I could just pick $\{b^{-n}\}$ and so every linear combination $ai+bj=n$, can be used to create an irregular language? I'm gonna reach the pumping lemma soon.. really excited! Thanks again! $\endgroup$
    – Pwaol
    Feb 17, 2022 at 20:26
1
$\begingroup$

There exists an infinite set of different irregular languages such that their union is a regular language, even on a one-letter alphabet. Indeed, let $L = \{a^{n^2} \mid n \geqslant 0\}$ and $L_n = L \cup \{a^n\}$. Then each $L_n$ is non-regular, but $$ \bigcup_\text{$n$ is a non-square integer} L_n = a^* $$ is regular. Moreover, if $n$ and $m$ are two distinct non-square integers, then $L_n \neq L_m$.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! I'm trying understand the way you built the example, I can understand intuitively why $L_n$ is irregular, for an automaton to accept it, it needs to always add new states and it must be finite, impossible. I think I got the idea of adding $a^n$ was to reach $a^*$, as $L$ will give us all the $a^k$ elements where $k$ is a square integer, and the rest will appear from the $\{a^n\}$ in the union for each non square integer. I just didn't get what you meant with your last sentence, what does that tell us? And again thanks for the help I learnt alot from studying your answer. $\endgroup$
    – Pwaol
    Feb 17, 2022 at 20:48
  • 1
    $\begingroup$ The last sentence means that the languages considered in the union are pairwise distinct, as required. $\endgroup$
    – J.-E. Pin
    Feb 18, 2022 at 5:24

You must log in to answer this question.

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