search
Log In
2 votes
181 views

Suppose that L is Context free and R is Regular.

  • $A$)  $L – R$ is necessarily Context free
  • $B$)  $R – L$ is necessarily Context free

Which of the above statement/s is/are true?

in Theory of Computation
retagged by
181 views
1
is it only $A$ ?
3
Yes, and 2nd one is false for CFL and even RE but not for others.
2
^yes.

A) True

B) False ( not necessarily), because CFL is not closed under complementation. R-L = R INTERSECTION L'
1
if L is DCFL , then B) is also true.

As DCFL closed under complement
0
@kapil u meant R-L is not R.E when L is RE right ? and true when L is recursive right ?
0
If possible pease support ur answer with an example. It'll be helpful indeed. :)

1 Answer

1 vote
1) It's closure property. CFL is closed under Regular difference (Even every language is closed under regular difference).

2) R-L is not any standard thing , we have to do calculations to know about this so we can't say anything.

Related questions

4 votes
2 answers
2
526 views
$L1= \{a^mb^nc^k\;|\;if\,(m=n)\,then\,(n!=k)\} \\ L2= \{a^ib^jc^k\;|\;if\,(i<j)\,then\,(k<j)\}\\ L3= \{a^ib^jc^k\;|\;(i<j)\,\leftrightarrow \,(k<j)\}$ Could someone please help to conclude the class of above languages? Below mentioned is the logic used to conclude that L1 and L2 are CFL but ... ( i<j) and comp( k<j) ] or [ (i<j) and (k<j) ] = [ (i>=j) and (k>=j) ] or [ ( i<j) and ( k<j) ] = CSL
asked Nov 17, 2016 in Theory of Computation yg92 526 views
0 votes
0 answers
3
3 votes
1 answer
4
151 views
$L_1 =\{a^n b^m c^n \mid m,n \geq 0\}$ and $L_2=\{ a^n b^n\mid n\geq 0\}$. If $L=L_2-L_1$ then $L$ is finite language regular language DCFL not DCFL
asked Nov 10, 2017 in Theory of Computation Prateek Raghuvanshi 151 views
...