Are those two regular languages the same?

Question

Given an alphabet of {a,b} where Na denotes the number of occurrences of a, and Nb the number of occurrences of b:

1) L1 = {xy|Na(x)=Nb(y)}
2) L2 = {w|Na(w) is even, Nb(w) is even}

Wouldn't a single DFA with four states and using mod be able to accept both languages?

Answer 1

There is indeed a four-state DFA that accepts $L_2$. If the initial state and sole accepting state is $q_{00}$ and the other states are $q_{01},q_{10}$, and $q_{11}$, the transitions are

$$\begin{array}{cc} q_{00}\overset{a}\longrightarrow q_{10}&q_{00}\overset{b}\longrightarrow q_{01}\\ q_{10}\overset{a}\longrightarrow q_{00}&q_{10}\overset{b}\longrightarrow q_{11}\\ q_{01}\overset{a}\longrightarrow q_{11}&q_{01}\overset{b}\longrightarrow q_{00}\\ q_{11}\overset{a}\longrightarrow q_{01}&q_{11}\overset{b}\longrightarrow q_{10} \end{array}$$

which appears to be the machine that you had in mind.

Note, however, that $ab\in L_1$: just set $x=a$ and $y=b$ in the definition of $L_1$. However, $$q_{00}\overset{ab}\Longrightarrow q_{11}\;,$$ so this DFA that accepts $L_2$ does not accept all of $L_1$.

In fact $L_1=\{a,b\}^*$: every word over the alphabet $\{a,b\}$ is in $L_1$.

Proof. Let $w=x_1x_2\ldots x_r\in\{a,b\}^*$. Let $m=N_a(w)$ and $n=N_b(w)$; clearly $m+n=r$. Let $\alpha_0=0$ and $\beta_0=n$. Given $\alpha_k$ and $\beta_k$ for some $k<r$, let $$\alpha_{k+1}=\begin{cases}\alpha_k+1,&\text{if }x_k=a\\\alpha_k,&\text{if }x_k=b\end{cases}$$ and $$\beta_{k+1}=\begin{cases}\beta_k,&\text{if }x_k=a\\\beta_k+1,&\text{if }x_k=b\;.\end{cases}$$ For $k=1,\ldots,r-1$, $\alpha_k=N_a(x_1\ldots x_k)$, and $\beta_k=N_b(x_{k+1}\ldots x_r)$; $\alpha_r=m=N_a(w)$, and $\beta_r=0$. Think of $\langle\alpha_k,\beta_k\rangle$ as a point in the plane; then as $k$ runs from $0$ to $r$, the point $\langle\alpha_k,\beta_k\rangle$ moves from $\langle 0,n\rangle$ on the $y$-axis to $\langle m,0\rangle$ on the $x$-axis, in unit steps either to the right or down. At some point this path must intersect the diagonal $y=x$; thus, there is a $k\in\{0,1,\ldots,r\}$ such that $\alpha_k=\beta_k$. Let $u=x_1,\ldots x_k$ and $v=x_{k+1}\ldots x_r$; then $w=uv$, and $N_a(u)=\alpha_k=\beta_k=N_b(v)$, so $w\in L_1$. $\dashv$

Answer 2

No.

Consider the string $aaabbb$.

$aaabbb \in L_1$ can be seen if you let $x = aaa$ and $y = bbb$, but $aaabbb \notin L_2$, since $N_a(aaabbb) = N_b(aaabbb) = 3$ and are thus both odd.

Thus, the two languages can't be the same, as $aaabbb$ is in one, but not the other.