TOC | CSL Complement | Ace Pre Gate Question

Question

The complemment of the language {wwww|w is in ([email protected]+$)*}  is

• A.

  Regular

• B.

  CSL but not CFL

• C.

  CFL

• D.

  CSL

Answer

Can someone please explain how this language is CFL ?

 

Comments

From what I think is, CFL is closed under union so we have to look for components of the language, if they are all below or are CFL the language as a whole will be CFL.

e.g every string with length not equal to 4n would be part of the language, so a regular component.

Also all strings starting with (ww)' [CFL], ending with (ww)' [CFL] and containing (ww)' [CFL] and any component I'm missing, when we union all of them it'll come out to be CFL.