# Help on using the pumping lemma?

I'm trying to prove that a language is not regular. That language is:

{w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}.

I have an inkling that this language is not regular, so when I go to apply the pumping lemma, I would apply it on some subset of the language, and the pump on that, right? So, let's say I choose to pump on a, and then I'm able to produce a string that should be in the language, but it isn't. I can do this because when I pump on a, I can produce a string that is not in the language because it will not be the same mod 2. But, I am having a hard time understanding if this is really true. I'm trying to construct a DFA that is able to count the amount for a's and b's, but I'm not having much success. Am I right or wrong?

• Why are you trying to prove that? I am afraid it is hard to prove. Nov 21 '14 at 21:41
• Well, I do not want to discourage anyone. I remember a PhD student who worked on a problem that his advisor considered impossible to solve. The student was right, despite the very hish reputation of the advisor. However, here I want the student to talk, because finding out (as much as possible by himself) he is on the wrong track may teach him something. Nov 21 '14 at 22:01

This language is regular. Since you're looking for equivalences mod 2 we need only consider the evenness or oddness of the count of the two kinds of symbols in the input. Consider a finite automaton with four states: EE, EO, OE, OO, where state EE records that the number of $a$'s seen so far is even and the number of $b$'s is also even. Similarly, being in state EO means you've seen an even number of $a$'s and an odd number of $b$s. States OE and OO are defined similarly.
Now consider the transitions between states. For example, in state EO with input a, the number of $a$'s changes from even to odd, while the number of $b$'s doesn't change, so we have the transition $\delta(\text{EO}, a) = \text{OO}$. The other seven transitions are defined similarly.
The start state is EE, since you've seen 0 $a$'s and 0 $b$'s and obviously 0 is an even number. The final states are EE and OO, for obvious reasons.