3
$\begingroup$

I need to prove or disprove if these two languages are same. So I assume that these lanaguages are same because I think that every word from $\{a,b\}^*$ could be concatenated from two words $x$ and $y$ where $|x|_a = |y|_b$. So $x$ and $y$ must belong to $\{a,b\}^*$, too. Then I can write and prove this:

$\{a,b\}^* \subseteq \{xy \in \{a,b\}^* \mid |x|_a = |y|_b \} \wedge \{xy \in \{a,b\}^* \mid |x|_a = |y|_b \} \subseteq \{a,b\}^*$

So I assume that $z \in \{a,b\}^*$. Then $z = z_1z_2...z_i$ where $z_1,z_2,...,z_i \in \{a,b\}$

Here I stucked and I don't know (1) how to continue, (2) if the way of proving i choose is correct or not.

$\endgroup$
2
$\begingroup$

You can prove this by induction on the length of the string.

The base case of $|z| = 0$ is obvious, we have to take $x=y=\varepsilon$.

The inductive assumption then is that $L =\{xy \in \{a,b\}^{\ast}\mid |x|_{a} = |y|_{b}\}$ contains all strings1 of length at most $n$.

Now we want to show that it contains all strings of length $n+1$.

Let $z \in \{a,b\}^{n+1}$ and let $z^{-1}$ be $z$ with the final symbol removed. By the inductive assumption $z^{-1} \in L$. The final symbol $z_{n+1}$ in $z$ must be either an $a$ or a $b$.

  1. If $z_{n+1}$ is an $a$, then we can construct an appropriate $x_{z}$ and $y_{z}$ by taking $x_{z} = x_{z^{-1}}$ and $y_{z} = y_{z^{-1}}a$. Then $|x_{z}|_{a} = |x_{z^{-1}}|_{a} = |y_{z^{-1}}|_{b} = |y_{z}|_{b}$, and therefore $z\in L$.

  2. If $z_{n+1}$ is a $b$ we have a slightly more complicated situation, but it's not too difficult. The first symbol of $y_{z^{-1}}$ must also be either an $a$ or a $b$, or $y = \varepsilon$.

    • If the first symbol is an $a$, then we use the same $x$-$y$ partition as for $z^{-1}$, but we move the first symbol of $y$ to the end of $x$, and add the new $b$ to the end of $y$, then $|x_{z}|_{a} = |x_{z^{-1}}|_{a} + 1$ and $|y_{z}|_{b} = |y_{z^{-1}}|_{b} + 1$.

    • If the first symbol is a $b$, we do the same as in the $a$ case, but as we're adding a $b$ to $x$ and taking one $b$ away from $y$ but adding another at the end, the number of $a$s and $b$s in $x$ and $y$ don't change.

    • If $y_{z^{-1}} = \varepsilon$, then we simply choose $x = z$ and $y = \varepsilon$ and again $|x_{z}|_{a} = |x_{z^{-1}}|_{a} = |y_{z^{-1}}|_{b} = |y_{z}|_{b}$ (in fact, they all equal $0$, so $z = b^{n+1}$).

Therefore in all cases $z \in L$, and we are done.

Footnotes

  1. ...over alphabet $\Sigma = \{a,b\}$.
$\endgroup$
2
$\begingroup$

We want to show that every string $z\in \{a,b\}^*$ is of the form $xy$ with $|x|_a=|y|_b$, as follows.

Make a graph of the value $|x|_a - |y|_b$ for every composition $x,y$ of $z = xy$, letting $x$ run over the prefixes of $z$. The value starts at $-|z|_b$ for $x=\varepsilon$ and ends in $|z|_a$ for $x=z$. Carefully argue it will be zero somewhere on the way.

$\endgroup$
  • $\begingroup$ In his answer to a related question Gilles observes that in fact we can take $|x| = |z|_b$. Clever! $\endgroup$ – Hendrik Jan Mar 7 '17 at 8:31

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.