Question

Construct a regular grammar G = {V,T,S,P} such that L(G)= L(r) where r is a regular expression (a+b)a(a+b)*.

Question 10 Construct a Regular grammar G = (V, T, S, P) such that L(G) = L(r) wherer is the regular expression (a+b)a(a+b). B I VA A IX E 12 XX, SEE 2 x G 14pt Paragraph

Answer 1

Answer ----

A -> aB / bB

B -> aC

C -> aC / bC / ε

A grammar is regular if we have productions of form P->aQ or P->a or P->ε . So here in this problem we have to create regular grammar for (a+b)a(a+b)* . It means initially there can be either 'a' or 'b' then second symbol will be 'a' and then any number of a's or b's. So we first generate first symbol by A->aB / bB it means firs symbol is either 'a' or 'b' followed by non terminal B . Now this B generates aC it means second symbol is 'a'. Now C generates aC , bC or ε . It means C can generate any number of a's and b's. So above is regular expression for this given grammar.