2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Why are you trying to prove that? I am afraid it is hard to prove. $\endgroup$
    – babou
    Commented Nov 21, 2014 at 21:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – babou
    Commented Nov 21, 2014 at 22:01

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The more general point here is that you only need to remember a finite number of things, so you can use the states of a finite automaton to do that. The answer I wrote to a somewhat different question about automata might help you think about designing automata based on what the different states "mean". $\endgroup$
    – David Richerby
    Commented Nov 21, 2014 at 21:51
  • $\begingroup$ In fact you can have an even simpler DFA, because the criterion is equivalent to "length of w is even". $\endgroup$
    – psmears
    Commented Jan 3, 2015 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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