Question

Give context free grammars for the languages below. To avoid mistakes, I recommend using scratch paper to check that your grammars produce the right set of string. This question is structured so that nonterminals (and associated rules) from an earlier subquestion might be useful in a grammar for a later sub-question. That’s why, rather than “S” as the start symbol, we will used different start symbols for each part. If you do use a nonterminal from an earlier sub-question, say something like “see part a”.

Let sigma ( Σ ) be the set {a, b}

a. All possible strings over sigma including the empty string. Use P as the start symbol.

b. Stings over sigma that contain no b's (and any number of a's). Use T as your start symbol.

c. Strings over sigma that contain exactly one b (and any number of a's) Use U as your start symbol.

d. Strings over sigma that contain exactly two b's (and any number of a's)  Use V as your start symbol

e. Strings over sigma that contain exactly three b’s (and any number of a's) Use W as your start symbol.

f) Strings over sigma that contain at most three b's (and any number of a's). Use X as your start symbol

f. Strings over sigma that contain a multiple of three b's (and any number of a's). (including strings with b's at all). Use Y as your start symbol.

Answer 1

a)

P -> PaP | PbP | a | b | epsilon

It will take empty string epsilong and all other strings of combination of a and b can be formed.

b)

T -> aT | epsilon

Here any number of a will come and ends by epsilon but no b will come.

c)

U -> TbT | b

T -> aT | epsilon (from b)

Any number of a will come before and after b.

d)

V -> UU

U -> TbT | b (from c)

T -> aT | epsilon (from b)

There were exactly one b in c and we use it 2 times for exactly 2 b.

e)

W -> UUU

U -> TbT | b (from c)

T -> aT | epsilon (from b)

There were exactly one b in c and we use it 3 times for exactly 3 b.

f)

X -> T | U | V | W

V -> UU (from d)

W -> UUU (from e)

U -> TbT | b (from c)

T -> aT | epsilon (from b)

Atmost 3 b means b can be 0, use T, can be 1, use U, can be 2, use V, and can be 3, use W.

g)

Y -> YW | epsilon

W -> UUU (from e)

U -> TbT | b (from c)

T -> aT | epsilon (from b)

Here W gives exactly 3 b. And Y can be any number of times of W means any number of times of 3, i.e., b will be in multiple of 3.