Question

1. Write grammars for:
a. aⁿb²ⁿ
b. abⁿa :n is multiple of 3
c. aⁿ b aⁿ⁺¹
d. C proc def: <type> id ( param_list )
where a param_list is 0 or more declarations of form “<type> id ;”

Answer 1

a)

S=> aSbb|$\epsilon$

The above given grammar will accept all the string which has twice the number of b's compared to number of a's.

Example: abb, aabbbb, aaabbbbbb, aaaabbbbbbbb, aaaaabbbbbbbbbb,... etc.

b)

S=> aSa|b

The string generated by the grammar will start and end with a.

Example: aba. aabaa, aaabaaa, aaaabaaaa, aaaaabaaaaa, ....etc

c)

S=> AbAa

​A=> a

the generated string will starts from a containing one more a than number of a's present before b.

Example: abaa, aabaaa, aaabaaaa, aaaabaaaaa, aaaaabaaaaaa, ....etc.