edited by
2,437 views
17 votes
17 votes

Which of the following statements is FALSE?

  1. The intersection of a context free language with a regular language is context free.
  2. The intersection of two regular languages is regular.
  3. The intersection of two context free languages is context free
  4. The intersection of a context free language and the complement of a regular language is context free.
  5. The intersection of a regular language and the complement of a regular language is regular.
edited by

4 Answers

10 votes
10 votes

a) abn  ∩  ab(m=n) = an b(which is CFL)

b) abn  ∩  ak bl   = ay b(RL)

c)abnck(m=n)  ∩  aibnck(n=k) = ambnck(m=n=k) (this CSL NOT CFL) (FALSE)

d)CFL ∩ (∑*-RL)  = CFL =CFL

e)RL ∩ (∑*-RL)  = R∩ =RL

//up vote if you agree

0 votes
0 votes
option C is FALSE. Context free languages are not closed under intersection.
Answer:

Related questions

10 votes
10 votes
2 answers
3
makhdoom ghaya asked Nov 4, 2015
1,037 views
Let there be a pack of $100$ cards numbered $1$ to $100$. The $i^{th}$ card states: "There are at most $i - 1$ true cards in this pack". Then how many cards of the pack c...