recategorized by
3,286 views
21 votes
21 votes
State whether the following statements are TRUE or FALSE:

The intersection of two CFL's is also a CFL.
recategorized by

4 Answers

Best answer
31 votes
31 votes

No intersection of two CFLs may or may not be a CFL i.e. CFL is not closed under intersection operation.

Example:

  • $L_1: \{ a^nb^nc^m| n,m >=1 \} \cap L_2: \{ a^nb^mc^m | n,m >=1 \}$
  • $L_3= \{ a^mb^mc^m | m >=1 \}$,  which is CSL.
edited by
0 votes
0 votes

FALSE,  as CFL’s are not closed under intersection operation and hence intersection of two CFL’s may or may not be a CFL. It could be CSL also.

Answer:

Related questions

14 votes
14 votes
2 answers
1
makhdoom ghaya asked Nov 9, 2016
3,881 views
State whether the following statements are TRUE or FALSE:The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.
14 votes
14 votes
4 answers
2
makhdoom ghaya asked Nov 9, 2016
3,493 views
State whether the following statement are TRUE or FALSE.$A$ is recursive if both $A$ and its complement are accepted by Turing machines.
13 votes
13 votes
2 answers
3
makhdoom ghaya asked Nov 9, 2016
2,462 views
State whether the following statements are TRUE or FALSE:All subsets of regular sets are regular.
17 votes
17 votes
5 answers
4
makhdoom ghaya asked Nov 9, 2016
3,616 views
State whether the following statements are TRUE or FALSE:Regularity is preserved under the operation of string reversal.