2
$\begingroup$

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}\}. $$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 9 '17 at 13:28
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Could you explain what the x0y notation means? $\endgroup$ – dfwef3 Mar 9 '17 at 14:52
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 9 '17 at 14:53
  • $\begingroup$ Two days ago we had that language! Is language $\{a,b\}∗$ same as language $\{xy\in \{a,b\}^∗\mid |x|_a=|y|_b\}$ ? $\endgroup$ – Hendrik Jan Mar 9 '17 at 18:03
  • $\begingroup$ @HendrikJan Indeed, the language had appeared even before that. It's a nice tricky exercise. $\endgroup$ – Yuval Filmus Mar 9 '17 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.