The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
71 views
Cfl is closed under intersection with regular language.

Then resultant languages will be regular or cfl ?

Let X is cfl

Y is regular language

 L=X intersection Y

Then L is what?
asked in Theory of Computation by (159 points) | 71 views
0
Every regular language is also a CFL.
0
Then resultant language will be what?
+1
CFL
0
Thank you so much to clear my doubt.
0
"Cfl is closed under intersection with regular language." means it will always be the case any CFL with any regular language will always be regular.

But we have a statement: "CFL is not closed under complementation" does not mean it will never be a CFL, It means it MAYor MAY NOT be a CFL.

2 Answers

+1 vote
Best answer
  1. CFL intersection REG ----> CFL is closed intersection with regular language . Means
  • intersection may be regular hence it is also cfl. 
  • Intersection may be cfl .

So it always gives CFL .but not above the  CFL .

answered by Boss (22.5k points)
selected by
0 votes
Let's take an exaple

X=$a^n$$b^n$|n>=0 -CFL

Y=$a^m$$b^n$|m,n>=0 -regular

$a^nb^n\bigcap a^mb^n=a^nb^n$ ,which is CFL
answered by Loyal (5.2k 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

37,964 questions
45,466 answers
131,324 comments
48,379 users