Theory of Computation

CS 3810, Spring 2020

Name:

Quiz 07.1

1. (C7) Prove the context-free grammar given below is ambiguous. Note Σ = {(, ),{,},a}.

S → (S) | {S} | SS | M M → aM | �

2. (C8) Is the following grammar ambiguous? Support your answer.

S → aSb | B B → bb

3. (C9) Prove the following language is context-free.

L1 = {aibjck, i ≥ 0,j ≥ 0,k ≥ 0 and i = j or j = k}

4. (C10) Prove the following language is not context-free using the pumping lemma for context-free lan- guages.

L2 = {aib2iai, i ≥ 0}