Construct, in each case, a DFA/NFA that recognises L ( G ), where G is a regular grammar with productions (a) S _→ b | aS | aA, A _→ a | aA | bS. (b) S _→ aS | bS | aA, A _→ bB, B _→ aC, C _→ ε....

Construct, in each case, a DFA/NFA that recognises
L(G), where
G
is a regular grammar with productions

(a)
S
_→
b|aS|aA, A
_→
a|aA|bS.

(b)
S
_→
aS|bS|aA, A
_→
bB, B
_→
aC, C
_→
ε.

Design NFAs and DFAs that accept the following languages:

(a)
a+ ∪
b∗a∗
.

(b)
aa∗(a
∪
b).

(c) (a
∪
bb)∗(ba∗ ∪
ε).

(d) (ab∗aa
∪
bba∗ab).

(e) Complement of (ab
∗
aa
∪
bba∗ab).

(f) (aa∗ ∪
aba∗b∗).

(g) (a
∪
b)∗b(a
∪
bb)∗
.

(h) (abab)∗ ∪ (aaa∗ ∪
b∗).

(i) ((aa∗)∗b)∗
.

(j) (ab∗a∗) ∪ ((ab)∗ba).

(k) (ab∗a∗) ∩ ((ab)∗ba).

(l) (a
∪
b)a∗ ∩
baa∗
.

(m) (aa
∪
bb)∗(ab
∪
ba)(aa
∪
bb)∗
.

(n) (aaa)∗b
∪ (aa)∗b.

(o) (a(ab)∗(aa
∪
b) ∪
b(ba)∗(a
∪
bb))∗
.