Skip to main content
Added a summary of the proof.
Source Link
Jurij
  • 74
  • 4

Answer to your first question http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf.

A summary of the proof given in the link. First, it is shown that proving $L \cap R$ is CFL reduces to proving that $L \cap R'$ is CFL, where $R'$ is a regular language recognized by a DFA with exactly one final state. Then from the grammar for L (in Chomsky normal form) and DFA for R' a new grammar for $L \cap R'$ is constructed using a few straightforward rules.

Answer to your first question http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf.

Answer to your first question http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf.

A summary of the proof given in the link. First, it is shown that proving $L \cap R$ is CFL reduces to proving that $L \cap R'$ is CFL, where $R'$ is a regular language recognized by a DFA with exactly one final state. Then from the grammar for L (in Chomsky normal form) and DFA for R' a new grammar for $L \cap R'$ is constructed using a few straightforward rules.

Source Link
Jurij
  • 74
  • 4

Answer to your first question http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf.