Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
We 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. –  David Lewis Mar 24 '12 at 1:28
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.