<p>Answer to your first question <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf" rel="nofollow">http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-11T21:14:56.090Z
Could you please include some more details to make the answer more self-contained?
Dave Clarke
CC BY-SA 3.0
2013-03-11T22:53:15.543Z
Tanks! This is what I was looking for :-)
Ronny
CC BY-SA 3.0
2013-03-12T20:21:14.643Z
Added a summary of the proof to make it more self-contained.
Jurij
CC BY-SA 3.0
2013-03-11T16:20:11.697Z
2013-03-12T20:07:45.660Z
2013-03-12T20:07:45.660Z
Jurij
<p>This is a classical cross-product construction, originally published
by Bar-Hillel, Perles and Shamir (1961) in <code>On formal properties of
simple phrase structure grammars.</code>It can be found in most elementary
books on automata theory. (the reference to the initial paper appears in the paper suggested by @Jurij, which I could not access as I wrote this answer).</p>

<p>Actually, it can be done with any CF grammar, no normal form being
required (but ... see below).  On the FSA side, any recognizing
finite-state automaton will do, including non-deterministic.</p>

<p>The complexity is $O(n^{p+1})$ for both the construction time and the
size of the resulting grammar, where $n$ is the number of states of the
automaton and $p$ is the length of the longest rule right-hand side of
the grammar.</p>

<p>Hence, reducing the grammar in Chomsky normal form (CNF) will give $n=2$ and
allow for cubic time and space (and result size) complexity. More precisely, some of the constraints of CNF are not even needed. It is enough to put it in 2-form, by introducing new non-terminal so that no right-hand side containt more than 2 symbols.</p>

<p>The size of the resulting grammar can be
further reduced by minimizing the finite automaton.</p>

<p><a href="http://en.wikipedia.org/wiki/DFA_minimization" rel="nofollow">Minimizing a DFA</a> has a time complexity $O(ns \ log\ n)$, where $n$ is
the number of states and $s$ is the size of the alphabet. However
the cost is much higher for a NDFA, as it is $O(2^n)$. There is no
escape from that if you have a NDFA to begin with, since this high
cost is needed for <a href="http://en.wikipedia.org/wiki/Determinization" rel="nofollow">determinizing the NDFA</a> which requires a powerset construction on the set of states.</p>

CC BY-SA 3.0
2013-06-09T17:50:01.437Z
2013-06-09T23:55:29.590Z
2013-06-09T23:55:29.590Z
babou
<p>It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ and one (a DFA) that accepts $R$. Than a further automaton (a PDA) is constructed that accepts $L \cap R$. This automaton can be converted to a context-free language.</p>

<p>Is there some literature that gives a proof without constructing automatons and constructs a context-free grammar that generates $L \cap R$ directly?</p>

<p>What I want to know actually: Given a context-free Language $L$ and a regular Language $R$. How many rules at most does a context-free grammar need to generate $L \cap R$?</p>

CC BY-SA 3.0
2013-06-10T19:43:46.750Z
If I may, I am curious as to why you asked that question.
babou
<regular-language><descriptive-complexity><context-free-languages>
Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules)
Ronny
# Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules)

(Asked by: username_0 on 2013-03-11)

It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ and one (a DFA) that accepts $R$. Than a further automaton (a PDA) is constructed that accepts $L \cap R$. This automaton can be converted to a context-free language.

Is there some literature that gives a proof without constructing automatons and constructs a context-free grammar that generates $L \cap R$ directly?

What I want to know actually: Given a context-free Language $L$ and a regular Language $R$. How many rules at most does a context-free grammar need to generate $L \cap R$?

**Tags:** regular-language, descriptive-complexity, context-free-languages
> **Comments:**
> **username_1**: If I may, I am curious as to why you asked that question.  

---

## 2 answers

### Answer by username_2 on 2013-03-11. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_3**: Could you please include some more details to make the answer more self-contained?  
> **username_0**: Tanks! This is what I was looking for :-)  
> **username_2**: Added a summary of the proof to make it more self-contained.  

---

### Answer by username_1 on 2013-06-09. Score: 2

This is a classical cross-product construction, originally published
by Bar-Hillel, Perles and Shamir (1961) in `On formal properties of
simple phrase structure grammars.`It can be found in most elementary
books on automata theory. (the reference to the initial paper appears in the paper suggested by @Jurij, which I could not access as I wrote this answer).

Actually, it can be done with any CF grammar, no normal form being
required (but ... see below). On the FSA side, any recognizing
finite-state automaton will do, including non-deterministic.

The complexity is $O(n^{p+1})$ for both the construction time and the
size of the resulting grammar, where $n$ is the number of states of the
automaton and $p$ is the length of the longest rule right-hand side of
the grammar.

Hence, reducing the grammar in Chomsky normal form (CNF) will give $n=2$ and
allow for cubic time and space (and result size) complexity. More precisely, some of the constraints of CNF are not even needed. It is enough to put it in 2-form, by introducing new non-terminal so that no right-hand side containt more than 2 symbols.

The size of the resulting grammar can be
further reduced by minimizing the finite automaton.

[Minimizing a DFA](http://en.wikipedia.org/wiki/DFA_minimization) has a time complexity $O(ns \ log\ n)$, where $n$ is
the number of states and $s$ is the size of the alphabet. However
the cost is much higher for a NDFA, as it is $O(2^n)$. There is no
escape from that if you have a NDFA to begin with, since this high
cost is needed for [determinizing the NDFA](http://en.wikipedia.org/wiki/Determinization) which requires a powerset construction on the set of states.


---

