The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register
|
I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
necessarily Context free ??
+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?
context-free-language
theory-of-computation
identify-class-language
asked
Jan 7, 2017
in
Theory of Computation
by
dd
Veteran
(
57k
points)
retagged
Jul 4, 2017
by
Arjun
|
139
views
answer
comment
+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. :)
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
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.
answered
May 29, 2017
by
Rupendra Choudhary
Boss
(
14.4k
points)
comment
Please
log in
or
register
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
+2
votes
1
answer
1
Context Free Language
Is B context free? Please explain in detail.
asked
Jan 6, 2018
in
Theory of Computation
by
Shubham Kumar Gupta
(
449
points)
|
228
views
context-free-language
theory-of-computation
identify-class-language
regular-languages
grammar
+4
votes
2
answers
2
Identifying Context Free Language
$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 ... ( 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
by
yg92
Active
(
3.2k
points)
|
449
views
identify-class-language
context-free-language
theory-of-computation
0
votes
0
answers
3
Context free or not
How to understand such problems?
asked
Nov 20, 2017
in
Theory of Computation
by
Parshu gate
Active
(
3.1k
points)
|
124
views
context-free-language
identify-class-language
context-free-grammars
+3
votes
1
answer
4
context free language
$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
by
Prateek Raghuvanshi
Boss
(
10.6k
points)
|
118
views
context-free-language
identify-class-language
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
Recent Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
All categories
General Aptitude
1.9k
Engineering Mathematics
7.5k
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.3k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.5k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.5k
Others
1.5k
Admissions
595
Exam Queries
576
Tier 1 Placement Questions
23
Job Queries
72
Projects
17
Follow @csegate
Recent Blog Comments
Really helpful sir Thanks a ton👍👍
Amazing work Sir
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
50,644
questions
56,523
answers
195,611
comments
101,287
users