Choose correct option

Question

Choose the correct statement

(a) There exists a cfg generating the language $\{ ww \; \mid \; w\in (a+b)^+ \}$

(b) There exists a cfg generating the language $L= \{a^{n^2}\;\mid \; n\geq 1\}$

(c) There exists a cfg generating the language $\{a^nb^nc^n\;\mid \; n\geq 1\}$

(d) There exists a cfg generating the complement of the language $\{ ww \; \mid \; w\in (a+b)^+ \}$

The answer given is (d) .

But , in my opinion answer should be (a) . Am I wrong ? Please correct me. 

CFLs are not closed under complement. So , how can the answer be (d) ?

Answer 1

A. is clearly CSL.       // CFL can do string matching in reverse order like WW^r but not as WW
B. Power is quadratic . So it cant simulated by PDA .. LBA needed..
C. Again CSL. two infinite comparison on same variable 'n' simultaneously.. PDA cant simulate.
D. Yes complement of WW IS CFL.. How complement of CSL will be CFL ??

LET A be CFL & its complement is B which is CSL.. now some one asking what is complement of CSL 'B' ?? Obviously answer will be A which is CFL only..
CFG for complement of WW :
Every odd length string will be in complement of WW.

S(odd) ----> 0A | 1A | 0 | 1
A ---->  OS(odd) | 1S(odd)

Now for even length string :

S(even) ---->  BC | CB
B ----> DBD | 0
C ----> DCD | 1
D ----> 0 | 1

Answer 2

ww'| such that w not equal to w' 

so i will take 2 as (a+b)* and w' as epsilon.

so   (a+b)* . esp = ww'

now we have to check remove strting where w=epsilon and w'= epsilon(considerd above (static))

so   (a+b)* . esp - esp  =L(D')=(a+b)+

here d is the option.

so its regular and no need to build a complex simple DFA with 2 states adn a simple regular grammar can be made form this DFA.