Infinite intersection of regular languages

836 Views Asked by At

I need to disprove that an infinite intersection of different regular languages is a regular language, using the fact that the language $\{a^nb^n \mid n\ge0\}$ is not regular.

I am trying to define infinite number of different regular languages that their intersection will be equal this language, but I am not sure how to find those languages.

How can I do it?

1

There are 1 best solutions below

1
On

Let $L$ be any language that you know is not regular. Note that given any $w \in \Sigma^*$, the language $\{w\}$ is regular.
In particular, $\{w\}$ is regular for all $w \in \Sigma^* \setminus L$. Since regular languages are closed under complements, we see that $\Sigma^* \setminus \{w\}$ is also regular.

Now, note that $$L = \bigcap_{w \notin L}\left(\Sigma^* \setminus \{w\}\right)$$ and thus, we have written $L$ as an intersection of regular languages.

Note that the above is actually a countable intersection since $\Sigma^*$ is countable. (Assuming $\Sigma$ is finite, of course.)


Note that this idea also shows that every language (regular or not) can also be written as a union of regular languages. Indeed, $$L = \bigcup_{w \in L} \{w\}.$$