# How do I prove regular/non-regular with Nerode-Theorem? How to use it?

$$L_{1}=\left\{w \in\{a, b\}^{*} | \#_{a}(w)=0\right\}$$

$$L_{2}=\left\{w \in\{0,1\}^{*} | w=u v u \text { with } u, v \in\{0,1\}^{*}\right\}$$

I have problems to prove regularity with the nerode theorem

The idea behind this is that the nerode classes have to be finite for a regular language

How do I use this?

For L1 I know this

There is only $$b^{n}$$ due to the fact that there language does not accept any a

Let m$$\neq$$n than there exists $$b^{n}b$$ and $$b^{m}b$$ for all m $$\in \mathbb{N}$$\n an n $$\in \mathbb{N}$$\m and of all them are in L

For 2 I know this

Let vu be x so for all a,b $$\in \{0,1\}^{\star}$$ ax an bc are in L.

## 1 Answer

You'd have to prove that the equivalence relation for your language is of infinite index to show it isn't regular. If regular, the equivalence classes are exactly the states of tje minimum DFA for the language.

In this case, both are regular (if I understand the notation correctly, $$L_1$$ is just strings with no $$a$$; for $$L_2$$ you can take $$u = \epsilon$$ and $$v$$ the given string, so $$L_2 = \{1, 2\}^*$$). Nice red hering, BTW.

• So is my notation for the L1 proof correct? What do you mean by red hering? lol – Rapiz Feb 10 '20 at 2:38
• @Rapiz, they look non-regular, but are actually very simple languages. – vonbrand Feb 11 '20 at 15:15