Hello can someone give me advice to proof the following language are regular or not regular
$$ \begin{array}{l}{\text { 1. } L_{1}=\{x y \mid x, y \in\{a, b\}^* \text { and } \#_{a}(x)=\#_b(y)\}} \\ {\text { 2. } L_{2}=\left\{x c y \mid x, y \in\{a, b\}^{*} \text { and } \#_{a}(x)=\#_b(y)\right\}}\end{array} $$
I don't know how to start some advice would be nice. Thanks
On
$L_2$ is not regular.
Sketch of a proof by contradiction: Suppose it is regular. Let $p$ be the constant associated with the pumping lemma (# of states of a DFA which recognizes $L_2$). Consider the string $w=a^{p}cb^{p} \in L_2$. Divide $w=ijk$ such that $i=a^{p-1}, j=a$, and $k=cb^{p}$. The string $ij^{2}k=a^{p+1}cb^{p}$ is supposed to be in $L_2$ but it is clearly not - a contradiction.
$L_1$ is regular.
The strings in $L_1$ are of the form $R=b^{*}(ab^{*})^{m}(a^{*}b)^{n}a^{*}$ where $m=n$. That expression is almost a regular expression except for the presence of the parameters $m$ and $n$.
If $m < n$, then $R=b^{*}(ab^{*})^{m}(a^{*}b)^{n-m}(a^{*}b)^{m}a^{*}$. Let $R_1=b^{*}(ab^{*})^{m}, R_2=(a^{*}b)^{n-m}$, and $R_3=(a^{*}b)^{m}a^{*}$, so that $R=R_1R_2R_3$.
Let $w_i \in L(R_i)$, $1 \leq i \leq 3$.
Since $n-m>0$, $w_2 \neq \epsilon$.
(1) From the left end of $w_2$, move each letter into $w_1$ as long as it is a $b$. This is equal to appending more $b$'s to $w_1$, a step which still keeps the modified $w_1$ into $L(R_1)$.
(2) From the right end of $w_2$, move each letter into $w_3$ as long as it is an $a$. This is equal to prepending more $a$'s to $w_3$, a step which still keeps the modified $w_3$ into $L(R_3)$.
(3) If, during (1), we move all $n-m$ $b's$, then there's nothing left to do. The string $w_2$ is now empty. By the construction, the resulting string (which is still unmodified; we just viewed it differently) is still in $L(R)$.
(4) If, during (1), we encounter an $a$, then we know that at least one $b$ still exists in $w_2$, and it is at the right end of $w_2$. Move the $a$ into $w_1$ from the left end, while simultaneously moving the $b$ into $w_3$ from the right.
(5) Go back to (1).
Although a formal proof is required to show that the above process "turns" any string $w \in L(R)$, where $R=b^{*}(ab^{*})^{m}(a^{*}b)^{n}a^{*}$ with $m < n$ into a string belonging to a language where its regex has $m=n$, and although a similar proof is required for when $m \geq n$, it seems that $L(R) = L(R')$, where $R'=b^{*}(ab^{*})^{*}(a^{*}b)^{*}a^{*}$.
Do let me know if I missed something.
The language $L_2$ is not regular. If it was, its intersection with the regular language $a^*cb^*$ would be regular. But this intersection is $\{a^ncb^n \mid n \geqslant 0\}$, a language which is not regular (this can be easily proved by the pumping lemma or using Nerode's equivalence).
The language $L_1$ is equal to $\{a,b\}^*$ and hence is regular. It suffices to prove that every word $w$ can be written as $w = uv$ with $|u|_a = |v|_b$ (here I use the standard notation $|u|_a$ for the number of occurrences of $a$ in $u$). Let $w =c_1 \dotsm c_n$, where each $c_i$ is a letter. Consider the function $$ f(i) = |c_1 \dotsm c_i|_a - |c_{i+1} \dotsm c_n|_b $$ One has $f(0) = -|w|_b \leqslant 0$ and $f(n) = |w|_a \geqslant 0$. Furthermore, if $c_{i+1} = a$, then $$ f(i+1) = |c_1 \dotsm c_ia|_a - |c_{i+2} \dotsm c_n|_b = 1 + |c_1 \dotsm c_i|_a - |ac_{i+1} \dotsm c_n|_b = f(i) + 1 $$ Similarly, if $c_{i+1} = b$, then $f(i+1) = f(i)-1$. In other words, $f(i)$ goes from a non positive value to a non negative value by increments of $+1$ or $-1$. Therefore, it has to take at least once the value $0$, which gives for $w$ the wanted factorisation.