Awesome q2a theme
0 votes

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

  1. Regular

  2. CSL but not CFL

  3. CFL

  4. CSL


Can someone please explain how this language is CFL ?


in Theory of Computation by (5 points)
edited by | 27 views
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.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,106 questions
3,157 answers
95,958 users