Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement?
I have this Chomsky hierarchy in mind that I refer whenever closure properties between Type-m and Type-n languages are asked but sometimes I come up with a wrong result.
How do you people logically solve it? What is the best simplest way?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You have to prove that the intersection of a context-free language and a regular language is always context-free. The simplest proof might go through push-down automata. Given a push-down automaton for a context-free language $L_1$, it is not too hard to augment it so that the state of a DFA for the regular language $L_2$ is maintained, and given this, you can construct a push-down automaton for $L_1\cap L_2$. Other proofs are also possible.
Each such question should be considered on its own. There are no general tricks. You can't just rely on the diagram. The problem with relying on the diagram in this case is that the intersection of two context-free languages need not be context-free; so the fact that regular languages are context-free isn't enough to show that the intersection of a context-free language and a regular language is again context-free.
answered Jan 31, 2015 at 23:26