Finding the wrong regular expression

73 Views Asked by At

Which one of the following regular expressions does not define the language of all strings that ends with a.

  1. $(a + b)^*a$
  2. $b^*aa^*(bb^*aa^*)^*$
  3. $[a(ba)^* + b(ab)^*](a + b)^*a$
  4. $(b + aa^*b)^*a(a + bb^*a)^*$

So I thought the easiest way off solving this is taking a short string that is not obviously in all of them $bba$ and testing the expressions against that.

While typing this out I think I see the answer that eluded me on pen and paper, it looks like 4 cannot generate the string $bba$, is that correct?

1

There are 1 best solutions below

0
On BEST ANSWER

(3) is the only regular expression not defining the language of all words that ends with $a$. Indeed the word $a$ is not matched by this expression.

The three other expressions define what you want.