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.
Checking if the language is a regular one
-
0We need to be careful when using the existence of a regular expression to mean a language is regular. The regular expression feature in real-life programming languages and utilities has far more power than the formal regular expression concept in the theory of automata and formal languages. There are such real-life regular expressions to match your language $A$, but no formal regular expression. – 2012-03-24
2 Answers
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.
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$.