context-free-grammarformal-languages

write a cfg for the regular expression r=(a+b)*aa(a+b)*

CFG for Regular Expression r=(a+b)*aa(a+b)* I wrote the production as

 P:   S -> SaaS|aS|bS|E

and my other friends wrote

 P: S -> AaaA
    A -> aA|bA|E

Please, Which one is Correct?Its for a test. Will I get any mark?

Solution

  • Unfortunately, you've got it wrong. Notice that the grammar you wrote accepts the empty string. And clearly the regular expression requires at least aa to be present in the string. The second version makes sure this is indeed the case. Better luck next time!