Peter Linz Edition 4 Exercise 3.1 Question 5 (Page No. 75)

Question

what is the regular grammar for L={$a^nb^m$ | n+m is even}

Comments

comment what you get !

---

I am getting

S -> aS1 / bS2 / ε

S1 -> aS / bS3

S2 -> bS3

S3 -> bS2 / ε

---

Using Substitution rule, this Grammar can be further simplified.

$S \rightarrow aS_1 / bbS_3 / ε$

$S_1 \rightarrow aS / bS_3$                  

$S_3 \rightarrow bbS_3 / ε$                   $// $ $S3$ generates $(bb)^*$ i.e. Even number of $b's$

Using Substitution rule, this Grammar also can be further simplified.

$S \rightarrow aaS/ abS_3 / bbS_3 / ε  $        

$S_3 \rightarrow bbS_3 / ε$                   $// $ $S3$ generates $(bb)^*$ i.e. Even number of $b's$

Answer 1

Writing Regular Grammar for a language is much Harder than Making an FA for that language. In the GATE or other Objective exams, You will not be asked to write a Regular Grammar for a language. In GATE, You can simply eliminate the Grammars given in the Options by checking if they genertate the strings of the language or not. 

Now coming to the Question, To write Regular Grammar for any Regular language, the simplest method (sometimes time consuming maybe but Less Error Prone) will be to build a NFA and then write Right-linear Grammar from that FA. 

First Construct NFA for the given language and then directly write Right Linear Grammar from it. 

Or You can construct DFA and then Write Rigth linear Grammar from that. 

You can simplify the Grammar obtained and remove Useless symbols etc.

Practice writing Right linear Grammar from FA. 

Comments

@Deepakk Poonia (Dee)

In your dfa abab is not accept.

---

@abhishekmehta4u, Because it does not belong to the language.