Consider the language L = {an | n ≥ 0} ∪ anbn | n ≥ 0} and the following statements.

I. L is deterministic context-free

II. L is context-free but not deterministic context-free.

III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

A.

I only

B.

II only

C.

I and III only

D.

III only

Solution:

Statement I: True, L = {an | n ≥ 0} ∪ anbn | n ≥ 0}

                   

Since we can generate a deterministic PDA ∴ L is DCFL

Statement II: False, from the above statement since it is DCFL it is also CFL.

Statement III: True, 

Let, n = K + 1, L1 = {aK+1}, L2 = {aK+1bK+1}

Then: L = {aK+1} ∪ {aK+1bK+1} i.e L1 ∪  L2

Therefore, For any value of K we cannot distinguish between the two languages i.e. L1 and L2, because the ‘first of’ both the languages L1, L2 would be aK

∴ L is not LL(K) for any K.