Given the following grammar in BNF: string→ string string | a this corresponds to the set equation: S = SS ∪ {a} Show that the set S 0 = {a, aa, aaa, aaaa, . . .} is the smallest set satisfying the...

Given the following grammar in BNF:

string→ string string | a

this corresponds to the set equation:

S = SS ∪ {a}

Show that the set S₀
= {a, aa, aaa, aaaa, . . .} is the smallest set satisfying the equation. (Hint: First show that S₀does satisfy the equation by showing set inclusion in both directions. Then, using induction on the length of strings in S₀
, show that, given any set S’ that satisfies the equation, S₀must be contained in S’.)