Consider the following type 0 grammar over the alphabet = {a}. (i) Draw the total language

Consider the following type 0 grammar over the alphabet Σ = {a}.

(i) Draw the total language tree of this language to find all words of five or fewer letters generated by this grammar.
(ii) Generate the word a⁹ = aaaaaaaaa.
(iii) Show that for any n = 1, 2, . . . , we can derive the working string

AⁿBⁿD

(iv) From AⁿBⁿD. show that we can derive the working string

aⁿ²BⁿAⁿD

(v) Show that the working string in part (iv) generates the word

a⁽ⁿ⁺¹⁾²

(vi) Show that the language of this grammar is

SQUARE = {aⁿ² where n = 1 2 3 . . .}

= {a aaaa a⁹ a¹⁶ • • •}

Transcribed Image Text:

PROD 1 PROD 2 PROD 3 C PROD 4 PROD 5 PROD 6 PROD 7 PROD 8 PROD 9 S -a S → CD PROD 10 PROD 11 → ACB CAB AB - aBA Aa → aA Ba →aB AD→ Da BD →→ Ea BE→ Ea Ea