12,156 views
5 votes
5 votes
The intersection of a context free language  and a regular language

a)need not be regular

b)need not be context free

c) is always regular

d) is always  context free

4 Answers

Best answer
11 votes
11 votes
  • $a^nb^n \cap \phi = \phi$ which is regular, so option D). is true as it is regular $\Rightarrow$ CFL
  • $a^nb^n \cap \Sigma * = a^nb^n$ which is DCFL, hence option C). is false.
  • The above intersection shows that we can get the result CFL, but not regular. THis actually makes option A). also true as need not be regular means that atleast on one case it is not regular .
  • Hence, option D). and A). both are true .
edited by
5 votes
5 votes
Intersection of any language (Regular , DCFL , CFL , CSL , RC , RE) with Regular language is definitely closed.

Regular INTERSECT Regular -------- Regular

DCFL  INTERSECT Regular----------- DCFL

CFL  INTERSECT Regular----------  CFL

CSL   INTERSECT Regular ----------CSL

Recursive INTERSECT Regular --------- Recursive

Recursively Enumerable  INTERSECT Regular --------- Recursively Enumerable
------------------------------------------------------------------------------

According to this information , I think Option D is best....
reshown by
1 votes
1 votes

As we know

  • Every Regular Language is Context Free Language
  • But every Context Free Language needs not always to be Regular Language

so OPTION C IS CORRECT





Related questions

0 votes
0 votes
1 answer
1
mehul vaidya asked Sep 3, 2018
527 views
To find intersection of this two : If i proceed like thisregular ∩ CFG CFG ∩ CFG as regular lang is also CFGbut CFG is not closed under intersectionhence answer ma...
2 votes
2 votes
1 answer
4
Mahesha999 asked Dec 24, 2016
1,481 views
Does the below problem makes any sense? And if yes what is its answer? How?