Infinite intersection of regular language is not regular !

Question

Can someone give the intuition behind this ? Moreover an example will also be helpful ..

Answer 1

Let $x_1, x_2, x_3, \ldots$ be the sequence $0, 1, 4, 6, 8, 9, \ldots$ of non-prime, non-negative integers.

Let $a^{x_i}$ be a string of $x_i$ number of $a$’s (that is, $a^{x_3} = a^4 = aaaa$)

Let the language $L_i = a^* - \left \{a^{x_i} \right \}$.

Now consider $L =$ The infinite intersection of the sequence of languages $L_1, L_2, \ldots$. That is, $$L = \bigcap_{i=1}^{\infty}L_i = L_1 \cap L_2 \cap L_3 \cap \ldots$$

Note that $L = \left \{a^p \mid p \text{ is prime}\right \}$.

Hence L is not regular.

---

Another easy example would be (this one with unions as opposed to intersections):

Let $L_i = \left \{a^i b^i \right \}$ for some given value $i$.

Then, $L_1 = \{ab\}, L_2 = \{aabb\}, L_3 = \{aaabbb\}$ and so on.

Now consider $L =$ The infinite union of the sequence of languages $L_1, L_2, \ldots$ That is, $$L = \bigcup_{i=1}^{\infty}L_i = L_1 \cup L_2 \cup L_3 \cup \ldots$$

Thus, $L = \left \{ a^i b^i \mid \forall i > 0 \right \}$ which is CFL but not Regular.

Comments

Are you sure that a^(xi ) where xi is not prime is a regular language ?

---

@Aryana: No, $\left \{a^{x_i} \mid x_i \text{ is not prime} \right \}$ is not regular. However, Leen never claimed that it was.

When Leen said $L_i = a^* - \{a^{x_i}\}$, that $i$ is just one index. So $L_i$ is regular.

Then the infinite intersection $L = \bigcap_{i=1}^{\infty} L_i$ is not regular.

---

how is Li regular?

---

L_i is a regular language on 'a' which contains length of all strings except a^x_i where x_i is a non prime no.

How do we draw a DFA for it? If we were asked to make a DFA accepting strings of length not equal to 'n' where n is non prime no., then we would make a DFA having (n+2) states where the (n+1)th state would be the only non-final one.

But here there is no upper bound on the non-prime no.,x_i. It can go upto infinity. How can i make a finite automata?