1)

Let L be the language generated by the following grammar G:

S 1 S 1

S T

(2)

Show a context-free grammar for each of the following languages.

(1) L = {aⁱb^jc^k : i, j, k 0 and j = k}

(2) L = {aⁱb^jc^k : i, j, k 0 and either i = j or j = k}

(3) L = {aⁱb^j : i, j 0 and j = 4i + 2}

(4) L = BalDelim = {w : where w is a string of delimeters: (, ), [, ], {, }, that are properly balanced}

T 1 X 1

T X

X 0 X 0

X 1

List the first four elements of L in lexicographic order.