Automata: Regular Expression

Usually we prove that a language is not regular by using the Pumping Lemma (PL). But that's not very pleasant. Instead of looking at regular expressions, let's look at finite automata. A finite automaton has a finite number of states, and states is all you have in order to keep track of what you've done so far and, therefore, of what need to be done.

Here are some of the problems that our instructor Prof. Larmie Feliscuzo Santos give us that makes me bleed and I even consult it to science forums and here is what the reply....

1. regular expression for w contains even number of a's and b's
This is a regular expression because we never need more than 2 bits to remember where we are:
00 = we are OK
01 = we need another 'b'
10 = we need another 'a'
11 = we need another 'a' and another 'b'

Thus, we need 4 states:
OK ----a----> NEEDA
OK ----b----> NEEDB
NEEDA----a---->OK
NEEDA----b---->NEEDA&B
NEEDB----a---->NEEDA&B
NEEDB----b---->OK
NEEDA&B----a--->NEEDB
NEEDA&B----b--->NEEDA

This is tough:
( aa | bb | (ab|ba)(aa+bb)*(ab+ba) )*

2. every a is followed by b
This is simple: we just need one bit:
0 = we don't need a 'b'
1 = we need a 'b' right now

We have 2 states:
OK ----a---->NEEDB_NOW_
OK ----b---->OK
NEEDB_NOW_----b---->OK

(ab|b)*

3. palindrome: w = reverse of w
Impossible. If a string is palindrome and of length n, we need to remember n/2 characters to check that it is really palindrome. That n is unbounded, because if we fix a number of states, then we can enter a string that would need even more states. Remember that states =~ MEMORY.

I guess this is right. Thanks to the scienceforum especially to gandalf23.