# How does the union of two machines which accept language of form $0^{mx+b}$ look like

I am doing Shai Simonson's course on Theory of computation. I am not able to understand part b of one of its problem sets.

a. Prove that languages of form $$0^{mx+b}$$, where m and b are positive integer constants and x ranges from 0 to infinite, is regular.

b. Give an example of a regular set over the alphabet {0} which is not of form $$0^{mx+b}$$.

In the solution set, for part b, it is given that union of machines which accept language of form $$0^{mx+b}$$ describes a regular set, but is not of form $$0^{mx+b}$$.

Q1. I want to understand of what form the union is?

Q2.And also, we are talking about union of finite number of machines, right? Because the union of all such machines(which is infinite) will not be regular. Am I correct?

Q3. I would also like to know is there any other example of a regular language which is not of the given form but is regular.

Q4. I also want to clarify what does set of the union of two such machines will look like. Will it be {$$0^{2x_1+3}$$ $$\bigcup$$ $$0^{7x_2+4}$$} or {$$0^{2x+3}$$ $$\bigcup$$ $$0^{7x+4}$$} i.e. will the $$x's$$ be different or same in both the machines. I think the two sets are independent so they should be different but still want to confirm.

2. Indeed it should be finite otherwise it could be not regular. To prove this fact, for $$k\in \mathbb{N}$$, consider $$L_k = \{0^{n(2k+3)},n\in\mathbb{N}\}$$, and $$L = \bigcup\limits_{k\in\mathbb{N}}L_k$$. Then $$L$$ is the set of words over the alphabet $$\{0\}$$ that have a length which is the multiple of an odd number greater than $$2$$. That means that the complement of $$L$$ is $$\overline{L} = \{0^{2^n}, n\in\mathbb{N}\}$$. Since $$\overline{L}$$ is not even context-free, then $$L$$ cannot be regular.
3. $$L = \{0^{2n}, n\in \mathbb{N}\}\cup \{0^{3n}, n\in\mathbb{N}\}$$ satisfy the condition. To prove it, suppose $$L = \{0^{an+b}, n\in\mathbb{N}\}$$. Since $$\varepsilon \in L$$, then it means that $$b = 0$$. Since $$0^2\in L$$, it means that $$a\mid 2$$. Since $$0^3\in L$$, it means that $$a\mid 3$$. We conclude that $$a\mid\text{gcd}(2, 3) = 1$$, so that $$a = 1$$. Since it is clear that $$L \neq \{0^n, n\in\mathbb{N}\}$$ (because $$0^5\notin L$$ for example), $$L$$ is regular and not of the said form.
4. There seems to be a bit of misunderstanding about the variable $$x$$ here… And to be precise and avoid any mistake, you should write $$\{0^{2x+3}, x\in\mathbb{N}\}$$ instead of just $$0^{2x+3}$$. That way you will understand that $$x$$ is just a free variable and it does not matter how you write it.
• I think point 2, while correct for infinite unions of regular languages in general, would not be correct in this specific case? With $m=1$ and $b=1$, the language will be $\{0^n : n > 0\}$ which is regular. All the other languages of this form are its subsets, so the infinite union will result in a regular language. May 25 at 7:06
• @Ayush $\varepsilon \in L$ because $\varepsilon = 0^0 = 0^{2\times 0}$. Also $a\mid 2$ means that $a$ is a divisor of $2$. May 25 at 9:48