Checking if the language is a regular one

Question

Let A = $\{x \in \{a,b\}^{*} \mid |x|_{a} = |x|_{b} \}$. Is possible to find a regular expression $\alpha$ such that $L(\alpha)$ = A ? $L(\alpha)$ is the regular language defined by $\alpha$. It seems that A is not a regular language.

Answer 1

You’re quite right: $A$ is not regular. This is easily proved using the pumping lemma for regular languages; in fact, the argument given at Use of lemma to show that $\{a^nb^n:n\ge 0\}$ is not regular can be used virtually verbatim to show that $A$ is not regular.

Answer 2

You are right, the language $A$ is not regular. This can be proven using the pumping lemma.

Here is another nice proof: Assume that there is a deterministic finite state machine $M$ that recognizes $A$. If $M$ has $n$ states then, by the pidgeonhole principle, there are two words $a^i$ and $a^j$ ($i\neq j$) among $a,a^2,\ldots,a^{n+1}$ such that $M$ is in the same state after reading them. Then also the inputs $a^i b^i$ and $a^j b^i$ lead to the same state. This, however, is a contradiction since $M$ must accept $a^i b^i$ but reject $a^j b^i$.