Quiz 4 ROLL NO:____________________

 

CS 311 'Automata & Complexity Theory' Tuesday, June 11, 2002

Time: 10 min. Total marks: 10

      Open Book / Open Notes

 

Find the Right Linear Regular Grammar for the following langauge: [10]

S = {a,b}

L = { wS* | w contains at least one a and at most three b's }

 

Possible Solution:

 

S aA | baB | bbaC | bbbaD

A aA | bB | l

B aB | bC | l

C aC | bD | l

D aD| l