The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
41 views

Is this given answer correct?

asked in Theory of Computation by Junior (827 points)
edited by | 41 views
+1
yes, given answer is correct,

R' ∩ C' = ( R U C )' = C' ===> is it CFL closed under complementation? No ===> Is it CSL closed under Complementation? yes

therefore it must be CSL but it may or may not CFL

When CFL is DCFL then it is closed under complementation
0
R is regular so complement(R) is also regular as regular language are closed under complementation .

C is cfl so complement (C) is necessarily not cfl as cfl are not closed under complementation bt its is necessarily csl becoz cfl is subset of csl.

so intersection of csl and regular is definitely csl .(becoz regular are also csl and csl ∩ csl = csl as csl are closed under intersection)....

1 Answer

0 votes
Best answer
L1=regular so L1(complement) is also regular as well as CFL.

L2=CFL so its complement will be CSL .now $L1\bigcap L2$ will be CSL not CFL
answered by Active (1.9k points)
selected by
0
it may be CFL


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

40,927 questions
47,580 answers
146,425 comments
62,311 users