The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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 (169 points)
edited by | 99 views
Every regular language is also a CFL.
Then resultant language will be what?
Thank you so much to clear my doubt.
"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 (33.4k 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 Boss (10.1k points)

Related questions

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,117 questions
53,218 answers
70,454 users