# Regular expression for a language which doesn't look regular

I'm trying to find a regular expression for the following language:

$$L=\{x0y : \text{x contains same number of 0's as y contains 1's}\}.$$

• Usually I would ask what you have tried, but this is a trick question, which is hard to solve if you haven't seen the trick. – Yuval Filmus Mar 9 '17 at 13:28

The trick is to write $L$ as a different language. Let's consider the following similar language $$L' = \{ xy \in \{0,1\}^* : \#_0(x) = \#_1(y) \},$$ where $\#_0(x)$ is the number of 0's in $x$.

I claim that $L' = (0+1)^*$. Indeed, let $w = w_1\ldots w_n$ be some arbitrary word, and define $\delta_w(i) = \#_0(w_1\ldots w_i) - \#_1(w_{i+1}\ldots w_n)$. The following properties are not hard to check:

1. $\delta_w(0) \leq 0$.
2. $\delta_w(n) \geq 0$.
3. $\delta_w(i+1) = \delta_w(i) + 1$ for $0 \leq i \leq n-1$.

This shows that $\delta_w(i) = 0$ for some $0 \leq i \leq n$, and so $w \in L'$.

Your case is very similar - I'll leave you to figure out the details.

• Thanks. Could you explain what the x0y notation means? – dfwef3 Mar 9 '17 at 14:52
• It is the concatenation of three strings $x,0,y$. By the way, the first step toward solving a question is understanding it. You should have first asked for clarification regarding the question itself. – Yuval Filmus Mar 9 '17 at 14:53
• Two days ago we had that language! Is language $\{a,b\}∗$ same as language $\{xy\in \{a,b\}^∗\mid |x|_a=|y|_b\}$ ? – Hendrik Jan Mar 9 '17 at 18:03
• @HendrikJan Indeed, the language had appeared even before that. It's a nice tricky exercise. – Yuval Filmus Mar 9 '17 at 18:20