How to construct a CFG based on a given regular expression

Question

I am trying to figure out how to construct a CFG (context free grammar) based on a given regular expression. For example, a(ab)*(a|b) I think there is an algorithm to go through, but it is really confusing. here is what i got so far:

    S->aAB; 
    A->aAb|empty;
    B->a|b;

Does this look right? Any help would be appreciated.

Answer 1

Construct the CFG in three parts, each for a, (ab)* and (a|b).

For (a|b), you've got B -> a | b right.

(ab)* would mean strings like ab, abab, ababab and so on. So A -> abA | empty would be the correct production.

Hence, the full grammar becomes:

S -> aAB
A -> abA | empty
B -> a | b

Note: A -> aAb | empty would derive strings like ab, aabb, aaabbb and so on, which is not a regular language, and can't possibly represent a regular expression.