The Gateway to Computer Science Excellence
+2 votes
139 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 by Veteran (56.9k points)
retagged by | 139 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.
by Boss (14.3k points)
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
50,650 questions
56,208 answers
194,079 comments
95,112 users