1
$\begingroup$

I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading through proofs, I don't really understand the general idea of the proof itself. I'm not looking for a formal proof, but I am more concerned with understanding the high level idea. This is my basic idea for a proof, but there are some issues:

Given a regular language $R$ and a context free language $L$, the intersection of $R$ and $L$ is a context free language $L_1$. We know that there exists a DFA $D$ that recognizes $R$, as $R$ is a regular language. We also know that there exists a PDA $P$ that recognizes $L$, as $L$ is a context free language. Since it is a fact that $D$ can be converted into a PDA $P_1$, we know that $R$ is also a context free language. Next, we create a PDA with states as pairs of states from $P$ and $P_1$.

This is where I am getting stuck. How are the transitions modified to simulate both PDAs? And what happens to the stack?

$\endgroup$
0
$\begingroup$
  1. Look at the product construction for DFAs, it will give you a hint of what the state space of a PDA accepting the intersection will look like.

  2. You can convert $D$ to a PDA, but you have more information than that. It doesn't need to touch the stack at all, since it can be accepted by a DFA.

These should get you close to the answer.

$\endgroup$
0
$\begingroup$

Don't convert $D$ to a PDA.

Instead, you can construct a PDA that accepts $R \cap L$ by using the product construction on $D$ and $P$ -- check your favorite textbook on automata theory; it should be covered there. Basically, you take $P$, and then modify its control state using the product construction. See Intersection of context free with regular languages for more details.


You don't want to convert $D$ to a PDA, because that would require you to take a product construction of two PDAs, and there's no good way to do that (the intersection of two context-free languages is not context-free in general).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.