0
$\begingroup$

If $L=\{w \in \Sigma^*\mid w=uv,\text{ number of occurnce a's in $u$ equal to number of occurrence b's in $v$}\}.$

I think $L=\Sigma^*$ because for any string in $\Sigma^*$, we can split it to $uv$ such that it contain equal number of a's and b's. But I can't prove it or maybe that language isn't regular. Any help for prove that is a regular language or not are welcome.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

Indeed $L = \Sigma^\ast$. Here is a proof.

Clearly, $L \subseteq \Sigma^\ast$, so it suffices to show $\Sigma^\ast \subseteq L$. Let $w \in \Sigma^\ast$. We start with an arbitrary decomposition $w = uv$. If $|u|_a = |v|_b$ we are done. Otherwise, wlog let $|u|_a < |v|_b$. Then by moving the cutpoint one step to the right, i.e. considering the decomposition $uv_1, v_2 \ldots v_m$, we increase either the number of $a$s in $u$ (if $v_1 = a$) or decrease the number of $b$s in $v$ (if $v_1 = b$), so the absolute value of the difference $||v|_b - |u|_a|$ is reduced by $1$ after such a step. Since this difference is bounded from below by $0$ the procedure terminates after finitely many steps.

(If $\Sigma$ contains more symbols than $a, b$ the argument works the same way but the difference might stay the same in some steps.)

$\endgroup$