Find grammars for the following languages on a 1 L w w mo

Find grammars for the following languages on = {a}.

1. L = {w : |w| mod 3 > 0}

2. L = {w : |w| mod 3 = 2}

3. w = {|w| mod 5 = 0}

Solution

A context free grammar is defined as G = (N, T, P, S)
where
N is a set of non-terminal symbols.

T is a set of terminals where N n T = NULL.

P is a set of rules, P: N ? (N ? T)*, i.e., the left-hand side of the production rule P does have any right context or left context.

S is the start symbol

so for the first language the grammar comprises of

1.

G= {{S},{a},{S -> a|aa},S}

2.

G= {{S},{a},{S -> aa},S}

3.

G= {{S},{a},{S -> aaaaa},S}