Pumping lemma to prove the set of all words such that the sum of the number of 0s and 1s occurring in it is an even number is not regular

Question

In the alphabet {0, 1, 2}, how can I prove using the pumping lemma that there is not a regular expression that can describe the set of all words such that the sum of the number of 0s and 1s occurring in it is an even number, e.g. 222 and 02010 would be two such words, 2122 and 0201021 would not.

Answer 1

You can’t, because this language is regular. The easiest way to see this is to design a finite state automaton $M$ that recognizes the language. $M$ needs only two states, $q_0$ and $q_1$; $q_0$ will be the initial state and the only acceptor state. $M$ should change state whenever it reads a $0$ or a $1$, and it should remain in the same state whenever it reads a $2$. It’s not hard to check that it will be in state $q_0$ if and only if the total number of zeroes and ones that it has read is even.

There are standard techniques for deriving a corresponding regular expression from $M$.