in Theory of Computation
350 views
3 votes
3 votes
complement of CFL can never be CFL.

please explain if the above statement is true of false?
in Theory of Computation
350 views

3 Comments

Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular language and its complement are a pair of complementary context-free languages.
3
3

Thanx@Vishal_kumar98... 

so can I say that if a language is CFL but not regular then it's complement is not CFL as CFL is not closed under complement. 

0
0
False
0
0

3 Answers

1 vote
1 vote
False:

Compliment of CFL may or maynot be CFL.

4 Comments

Yes.

0
0
It is an even length palindrome which is accepted by NPDA and not by DPDA, which makes it CFL rather than being DCFL. So, how it is closed under complementation?
0
0
if I have got your question correct, closure properties apply to a class of languages, not to a specific language. When we say regular languages are closed under complementation, we mean any language from the whole class will still belong to that class, after the operation/combination. However, in this case, the language’s complement is CFL as well.
0
0
1 vote
1 vote
If the given CFL is a DCFL then complementation is closed. But if it is an NCFL which is not a DCFL then it may or may not be closed.

3 Comments

Can you give an example NCFL which is not DCFL but its complement is NCFL?
0
0

https://gateoverflow.in/203733/complement-of-cfl

If this is right, then NCFL complement can be NCFL in some cases

1
1

@gatecse I am not able to formulate any such example so I am not sure whether Complement of NCFL which is not a DCFL can also be NCFL, If I consider the standard NCFL’s like ww^r || a^i b^j c^k, i>=j or j<=k complement of them are always non NCFL.

0
0
0 votes
0 votes

@BHOJARAM

If the above statement is : False ...

CFLs are not closed under complement If L1 is a CFL, then L1 may not be a CFL….

They are closed under union.

If they are closed under complement, then they are closed under intersection, which is false...

 

 

1. https://gateoverflow.in/203733/Complement-of-cfl 

 

2. https://gateoverflow.in/6370/General-doubt

 

by

Related questions