A grammar G = (T,N,S,P) has T = {x,y,z}, N = {Z,A,B}, S = Z, and the following productions P:

Z A

A x y B

A x B z

B y B

B y

B z

Show that the above grammar is ambiguous.

Use the sentence x y z.

Part B (5 marks):

A program has been written that can simulate coin tosses until it generates two heads in a row. Write a grammar for a language whose sentences are the output from this program.

For example, valid sentences include hh, thtttttthh, hthh, thththttthh, and invalid sentences include h, thhhh, hhttthh, hthhtt, hhhtthhh.