recategorized by
1,495 views
2 votes
2 votes

Which one of the following statement is false ?

  1. Context-free languages are closed under union.
  2. Context-free languages are closed under concatenation.
  3. Context-free languages are closed under intersection.
  4. Context-free languages are closed under Kleene closure.
recategorized by

1 Answer

Best answer
2 votes
2 votes

C. CFL not closed under intersection.

One canonical example : $L_1 = \left \{ a^nb^nc^m \mid m,n \geq 1\right \}$  and $L_2 = \left \{ a^nb^mc^n \mid m,n \geq 1 \right \}$ both are CFL's

But $L_1 \cap L_2 = \left \{ a^nb^nc^n \mid n\geq 1 \right \}$ is not context free.

There are formal proofs regarding this non closure. One direct way is to say that, CFL's are not closed under complement => Also not closed under intersection.

We can also give informal proof from product automata point of view.

What we will do in product automata if we are to construct a PDA out of two given PDA's ?

let, $PDA_1$ and $PDA_2$ are two machines and we are going to build a machine using product automata which will represent intersection between these two machines.

To do that, we need to take each pairs of states between the states of $PDA_1$ and $PDA_2$. The pair forms a new state in the newly growing machine.We keep track of respective transitions in the constituent states simultaneously. While going through this prcedure we need to specify a state  (or configuration) in the newly forming machine ( = resulting machine). To specify a state of the resulting machine we must need to say, 4 things,

  • state of the $PDA_1$
  • state of the $PDA_2$
  • Stack config of $PDA_1$
  • Stack config of $PDA_2$ 

The resulting machine states are actually combined state consisting of two states from $PDA_1$ and $PDA_2$.

The moment we are going to describe a state in the resulting machiine using two different stack information, we are going beyond the realm of Context free language.

selected by

Related questions

1 votes
1 votes
2 answers
1
makhdoom ghaya asked Aug 21, 2016
2,821 views
The number of nodes in a complete binary tree of height $h$ (with roots at level $0$) is equal to$2^{0} + 2^{1} + ….. 2^{h}$$2^{0} + 2^{1} + ….. 2^{h-1}$ $2^{0} + 2^{...
1 votes
1 votes
4 answers
2
makhdoom ghaya asked Aug 21, 2016
3,414 views
What is the probability of choosing correctly an unknown integer between $0$ and $9$ with $3$ chances ?$\frac{963}{1000}$$\frac{973}{1000}$$\frac{983}{1000}$$\frac{953}{1...
1 votes
1 votes
2 answers
3
makhdoom ghaya asked Aug 21, 2016
1,433 views
A telephone conference call is an example of which type of communications ?Same time / same placeSame time / different placeDifferent time / different placeDifferent time...
1 votes
1 votes
2 answers
4
makhdoom ghaya asked Aug 21, 2016
2,915 views
Web Mining is not used in which of the following areas ?Information filteringCrime fighting on the internetOnline transaction processingClick stream analysis.