Doubt .... Theory of Computation ..... Regular Expression

Question

Design regular expression for no $2$  $a's$ should come together  ...... (Standard question in many text books)

 I came to know the answer is .... $(a + E) (b + ba)$ or $(b + ab) (a + E)$ ...... this I have understood Logically ....

but when I tried it on my own for the first time ... I came up with $(b + ab)^* + (b + ba)^{*} + a + E $....... please help me with any case or scenario where my expression fails.

This community is always helpful to me. Thanks in advance ...

Answer 1

• Regular expression for no two a's comes together is 

1. (a+$\epsilon$)(b+ba)*

2. (b+ab)*(a+$\epsilon$)

• Your regular expression (b+ab)*+(b+ab)* +a+ E  is not gives string like 'aba'.so it is wrong.

Comments

Sir , use ' * ' for Second Term in 1st one and first Term in Second one.

---

Ok

Answer 2

The expression (b+ab)* + (b+ba)* + a + E is wrong because it does not generate the string "abba"

The correct answer is (a+E)(b + ba)*