Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Intersection and concatenation in CFG
sh!va
asked
in
Theory of Computation
Feb 1, 2017
recategorized
Jun 21, 2022
by
Lakshman Patel RJIT
698
views
0
votes
0
votes
Given that L1 is regular and L2 context free.
i) L3 = L1 ∩ L2
ii) L4= L1.L2
Selct the most appropriate statement:
a. L3 , L4 are regular
b. L3 is regular L4 is CFG not regular
c. L3 is CFG, not regular L4 is regular
d. L3,L4 are CFG not regular
theory-of-computation
regular-language
context-free-grammar
sh!va
asked
in
Theory of Computation
Feb 1, 2017
recategorized
Jun 21, 2022
by
Lakshman Patel RJIT
by
sh!va
698
views
answer
comment
Follow
share this
share
1 comment
by
Sushant Gokhale
commented
Feb 1, 2017
reply
Follow
share this
is it D?
0
0
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
1
vote
1
vote
Best answer
Option D) is almost correct.
1) Intersection of CFL and regular is CFL but it may be regular too. For eg if L1 is $\epsilon$ which is regular then intersection of L1 with any langauage will be $\epsilon$ which is regular. So it is defintely CFL and may or may not be regular
2) Similarly concatenation is also closed for CFL. but in certain cases it may be regular. If L1 = $\phi$ then concatenation with always be phi which is regular.
So both are definetely CFL and may or may not be regular.
Kaushik.P.E
answered
Feb 1, 2017
selected
Feb 1, 2017
by
sh!va
by
Kaushik.P.E
comment
Follow
share this
0 Comments
Please
log in
or
register
to add a comment.
Answer:
D
← Previous
Next →
← Previous in category
Next in category →
Related questions
1
vote
1
vote
2
answers
1
vishal8492
asked
in
Theory of Computation
Dec 6, 2016
1,486
views
Regular Expression to CFG
So , 1 is mandatory in Regular expression ; and both of above grammar allows strings without 1 to be genearated. So , I expected None of above to be answer. What Am I missing here ? Consider for (A) Production = A0 -> A1 A1-> 0
vishal8492
asked
in
Theory of Computation
Dec 6, 2016
by
vishal8492
1.5k
views
theory-of-computation
regular-expression
context-free-language
context-free-grammar
regular-language
1
vote
1
vote
2
answers
2
Rahul Jain25
asked
in
Theory of Computation
Oct 9, 2016
895
views
Regular+CFG
Rahul Jain25
asked
in
Theory of Computation
Oct 9, 2016
by
Rahul Jain25
895
views
theory-of-computation
regular-language
context-free-language
context-free-grammar
bad-question
0
votes
0
votes
2
answers
3
smartmeet
asked
in
Theory of Computation
Jan 12, 2017
2,615
views
If L=(a+b)* and R=a*b*a* then L intersection R=?
We know, here R subset L so by formula R intersection L= R, but for any string R=L( both language are same) R intersection L can be R or L? Correct me!
smartmeet
asked
in
Theory of Computation
Jan 12, 2017
by
smartmeet
2.6k
views
theory-of-computation
regular-language
set-theory&algebra
0
votes
0
votes
1
answer
4
yg92
asked
in
Theory of Computation
Jan 25, 2017
344
views
Virtual Gate Test Series: Theory Of Computation - CFL Self Concatenation
Let $L$ be a given context-free language over the alphabet $\{a, b\}$ then $L_{2} = L·L$ is $\text{CFL.}$ Is $\text{CFL.}$ in general closed under $\text{self-concatenation?}$ If $L={ a^nb^n }$ then $L.L= { a^nb^na^nb^n }$ $\text{(or)}$ $L.L= { a^nb^na^mb^m } ?$
yg92
asked
in
Theory of Computation
Jan 25, 2017
by
yg92
344
views
theory-of-computation
regular-language
context-free-language
virtual-gate-test-series
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
From Rank 4200 to 64: My Journey to Success in GATE CSE Exam
What are the key things to focus on during the final 10-15 days before the GATE exam to improve performance?
All India GO Classes Mock test
NTA UGC NET JRF December 2022 Apply Online Form 2023
Life happens, just chill and do hardwork
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.8k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.6k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(649)
Exam Queries
(842)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(853)
Recent Blog Comments
Eligibility Criteria: Discipline of...
4-year B.Tech./B.E. degree or a MSc./MCA degree...
I am not sure about others but I would pay 2X...
@DebRC Yes. This, time stamp and comparing...
Small feedback for next year. It would be great...
Twitter
WhatsApp
Facebook
Reddit
LinkedIn
Email
Link Copied!
Copy