<p>This is a great question and it really lies within my interests.  I'm glad that you asked it Max.</p>

<p>Let $n$ DFA's with at most $O(n)$ states each be given.  It would be nice if there existed a PDA with sub-exponentially many states that accepts the intersection of the DFA's languages.  However, I suggest that such a PDA might not always exist.</p>

<p>Consider the copy language.  Now, restrict it to copying strings of length n.</p>

<p>Formally, consider $n$-copy $:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$.</p>

<p>We can represent $n$-copy as the intersection of $n$ DFA's of size at most $O(n)$.  However, the smallest DFA that accepts $n$-copy has $2^{\Omega(n)}$ states.</p>

<p>Similarly, if we restrict ourselves to a binary stack alphabet, then I suspect that the smallest PDA that accepts $n$-copy has exponentially many states.</p>

<p>P.S.  Feel free to send me an email if you would like to discuss further.  :)</p>

CC BY-SA 3.0
2014-11-08T23:46:49.327Z
2014-11-12T00:31:58.947Z
2014-11-12T00:31:58.947Z
Michael Wehar
<p>Let me second Michael's judgment, this is indeed an interesting
question. Michael's main idea can be combined with a result from the literature, thus providing a similar lower bound with a rigorous proof.  </p>

<p>I will refer to bounds on CFG size in terms of the total number of alphabetic symbols in the $n$ regular expressions. Let this number be denoted by $k$. (As john_leo noted, we will not find any useful bounds in terms of the number of regular expressions taking part in the intersection.)</p>

<p>Neither the OP nor Michael did find it necessary to mention this, but
an upper bound of $2^{k+1}$ (on the number of states) for converting
an intersection of regular expressions into a NFA can be easily
proved. For the record, here it is: Convert the regular expressions
into Glushkov automata, which are all non-returning. Then apply the
product construction to obtain an NFA for the intersection of these
languages. (I suppose that one can improve the bound to $2^k+1$ or
so.) An $s$-state NFA can be converted into a right-linear grammar
(which is a special case of a CFG) of size $O(s^2)$ (if we measure
grammar size as total number of symbols on the left- and
right-hand-sides of the productions), thus giving size $O(4^{k})$.
This bound of course sounds horrible if you have practical
applications in mind. Trying to prove a better bound using nondeterministic
transition complexity instead of nondeterministic state complexity for
estimating the size of the NFA may be worth the effort.</p>

<p>The other part is finding a witness language that can be succinctly expressed as the intersection of regular expressions, but is necessarily cumbersome to describe with a CFG. (Here we need to establish a lower bound on the size of all CFGs generating the language, of which there can be infinitely many.)
The following argument gives a $2^{\Omega(\sqrt{k}/\log k)}$ lower bound.</p>

<p>Consider the finite language $L_n = \{\,ww^Rw \in \{a,b\}^*\mid |w|=n\,\}$, where $w^R$ denotes the reversal of $w$. Then $L_n$ can be expressed as the intersection of the following $2n+1$ regular expressions:</p>

<ul>
<li>$r_i = (a+b)^ia(a+b)^{2(n-i-1)}a(a+b)^*+(a+b)^ib(a+b)^{2(n-i-1)}b(a+b)^*$, for $1\le i \le n$; </li>
<li>$s_i = (a+b)^*a(a+b)^{2(n-i-1)}a(a+b)^i+(a+b)^*b(a+b)^{2(n-i-1)}b(a+b)^i$, for $1\le i \le n$;</li>
<li>$\ell = (a+b)^{3n}$ </li>
</ul>

<p>The total number $k$ of alphabetic symbols in this intersection of expressions is in $O(n^2)$. </p>

<p>Using an argument given in the proof of Theorem 13 in (<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2304">1</a>), one can prove that every acyclic CFG that generates $L_n$ must have at least $2^n/(2n) = 2^{\Omega(\sqrt{k}/\log k)}$ distinct variables, if the right-hand side of each rule has length at most $2$. The latter condition is necessary for arguing about the number of variables, since we can generate a finite language with a single variable. But from the perspective of grammar size, this condition is not really a restriction, since we can transform a CFG into this form with only a linear blowup in size, see (<a href="http://www.informatica-didactica.de/cmsmadesimple/uploads/Artikel/LangeLeiss2009/LangeLeiss2009.pdf">2</a>). Notice that the language used by Arvind et al. is over an alphabet of size $n$, and this yields a bound of $n^n/(2n)$; but the argument carries over with obvious modifications.</p>

<p>Still, a large gap remains between $O(4^n)$ and the abovementioned lower bound.</p>

<p><strong>References:</strong></p>

<ul>
<li><p>V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan. <a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2304">Arithmetic Circuits and the Hadamard Product of Polynomials</a>, FSTTCS 2009, Vol. 4 of LIPIcs, pp. 25-36</p></li>
<li><p>Lange, Martin; Leiß, Hans (2009). "<a href="http://www.informatica-didactica.de/cmsmadesimple/uploads/Artikel/LangeLeiss2009/LangeLeiss2009.pdf">To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm</a>". Informatica Didactica 8.</p></li>
</ul>

CC BY-SA 3.0
2014-11-12T22:59:05.033Z
2014-11-12T22:59:05.033Z
Hermann Gruber
<p>I don't think that there can be any non-trivial lower or upper bounds.<br>
For lower bounds, consider the language $L_1 = \{ a^{2^k} \}$ for a fixed $k$. The size of the smallest context-free grammar is logarithmic in the size of $L_1$'s regular expression, whereas the size of the smallest automaton for $L_1$ is linear in the size of $L_1$'s regex. This exponential difference stays the same if we intersect $L_1$ with other such languages.<br>
For upper bounds, consider a language $L_2$ that consists of exactly one <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence" rel="nofollow">deBruijn-Sequence</a> of length $n$. It is known that the size of a smallest grammar for $L_2$ is worst-case, i.e. $O\left( \frac{n}{\log n} \right)$, so the difference to the "smallest" automaton for $L_2$ is simply a logarithmic factor, proposition 1 in</p>

<ul>
<li>D. Hucke, M. Lohrey, E. Noeth <a href="http://arxiv.org/abs/1407.4286" rel="nofollow">Constructing Small Tree Grammars and Small Circuits for Formulas</a>, to appear in FSTTCS 2014</li>
</ul>

<p>A non-trivial general lower or upper bound would contradict those results, since what is true for the intersection of $n$ languages must be true for the intersection of $1$ language.</p>

CC BY-SA 3.0
2014-11-12T01:27:32.220Z
The remark on the size of the smallest grammar for the single deBruijn-Sequence is quite interesting.  Could you please provide a reference.  Thank you.
Michael Wehar
CC BY-SA 3.0
2014-11-12T01:30:23.637Z
Also, I could be mistaken, but it seems that you only addressed the problem for a single regular expression (rather than a product of regular expressions)?
Michael Wehar
CC BY-SA 3.0
2014-11-12T09:35:56.503Z
@MichaelWehar Yep, I only considered one single regular expression. Because if it should be true for the intersection of $n$ languages, then it certainly must be true for the trivial intersection. I don't know how to reformulate the question to exclude these cases. I added the reference, should have done that right away, sorry.
john_leo
CC BY-SA 3.0
2014-11-14T00:45:06.307Z
Thank you!  You were able to describe a specific example.  Here is a simple remark that leads to the existence of such examples.  Let n be given.  There are 2^n strings of length n.  Also, there are no more than 2^n Turing machines with at most n/log(n) states.  Therefore, some string x of length n such that no Turing machine with fewer than n/log(n) states accepts the language {x}.  Therefore, {x} is accepted by a DFA with n states and cannot be accepted by a PDA with fewer than n/log(n) states.
Michael Wehar
CC BY-SA 3.0
2014-11-11T09:32:21.387Z
2014-11-12T09:29:11.347Z
2014-11-12T09:29:11.347Z
john_leo
<p>Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?</p>

CC BY-SA 3.0
2014-07-06T00:14:40.403Z
??? trying to visualize this. is there some trick? the intersection of $R_n$ is regular. one can find the minimal DFA (wrt state count) via standard methods which is also a CFG.
vzn
CC BY-SA 3.0
2014-07-06T08:24:16.030Z
@vzn: you are right. The problem is that this DFA, and therefore the CFG, can be very large. I'm wondering if one can use the extra power of CFGs to obtain a more succinct description of the intersection.
Max
CC BY-SA 3.0
2014-07-06T15:30:20.553Z
conjecture not. suspect that every CFL that recognizes (ie is equivalent to) a RL does not use its stack or can be converted to one that doesnt with no increase in states, and the minimal such PDA (wrt state count) is the same size as the minimal DFA. have never heard/seen a proof of this. its maybe not hard? a simpler question, is there _any_ PDA that recognizes a RL that is smaller than the DFA? think not.
vzn
CC BY-SA 3.0
2014-07-06T16:03:47.370Z
@vzn: Useful conjecture, but false: let $L_k$ be the subset of the Dyck languages on two types of parentheses where the maximum nesting depth is $k$. There is a CFG for $L_k$ of size $O(k)$, but the minimal DFA (even, I think, the minimal NFA) has size $O(2^k)$.
Max
CC BY-SA 3.0
2014-07-06T16:13:14.757Z
[Dyck languages](http://en.wikipedia.org/wiki/Dyck_language) are CFLs but not RLs...? but see you are limiting maximum nesting depth... so then can you build up that same language with RL intersections? what/where is the proof that the minimal DFA is that large? is that $O(2^k)$ _states_? you do not define a minimality criteria or elsewhere & took states as a natural case but ofc its not the only one.
vzn
CC BY-SA 3.0
2014-07-06T17:38:06.447Z
further thought/idea based on yours maybe $L_1' \cup L_2' \cup L_3' ...$ where $L_n'=\bar{L_n}$ and $L_k$ are Dyck languages with maximum nesting depth $k$ is sufficient?
vzn
<fl.formal-languages><regular-language><context-free>
Complexity of intersection of regular languages as context-free grammars
Max
# Complexity of intersection of regular languages as context-free grammars

(Asked by: username_0 on 2014-07-04)

Given regular expressions $R\_1, \dots, R\_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R\_1 \cap \cdots \cap R\_n$?

**Tags:** fl.formal-languages, regular-language, context-free

> **Comments:**
> **username_1**: ??? trying to visualize this. is there some trick? the intersection of $R_n$ is regular. one can find the minimal DFA (wrt state count) via standard methods which is also a CFG.  
> **username_0**: @username_1: you are right. The problem is that this DFA, and therefore the CFG, can be very large. I'm wondering if one can use the extra power of CFGs to obtain a more succinct description of the intersection.  
> **username_1**: conjecture not. suspect that every CFL that recognizes (ie is equivalent to) a RL does not use its stack or can be converted to one that doesnt with no increase in states, and the minimal such PDA (wrt state count) is the same size as the minimal DFA. have never heard/seen a proof of this. its maybe not hard? a simpler question, is there _any_ PDA that recognizes a RL that is smaller than the DFA? think not.  
> **username_0**: @username_1: Useful conjecture, but false: let $L_k$ be the subset of the Dyck languages on two types of parentheses where the maximum nesting depth is $k$. There is a CFG for $L_k$ of size $O(k)$, but the minimal DFA (even, I think, the minimal NFA) has size $O(2^k)$.  
> **username_1**: [Dyck languages](http://en.wikipedia.org/wiki/Dyck_language) are CFLs but not RLs...? but see you are limiting maximum nesting depth... so then can you build up that same language with RL intersections? what/where is the proof that the minimal DFA is that large? is that $O(2^k)$ _states_? you do not define a minimality criteria or elsewhere & took states as a natural case but ofc its not the only one.  
> **username_1**: further thought/idea based on yours maybe $L_1' \cup L_2' \cup L_3' ...$ where $L_n'=\bar{L_n}$ and $L_k$ are Dyck languages with maximum nesting depth $k$ is sufficient?  

---

## 3 answers

### Answer by username_2 on 2014-11-08. Score: 8

This is a great question and it really lies within my interests. I'm glad that you asked it username_0.

Let $n$ DFA's with at most $O(n)$ states each be given. It would be nice if there existed a PDA with sub-exponentially many states that accepts the intersection of the DFA's languages. However, I suggest that such a PDA might not always exist.

Consider the copy language. Now, restrict it to copying strings of length n.

Formally, consider $n$-copy $:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$.

We can represent $n$-copy as the intersection of $n$ DFA's of size at most $O(n)$. However, the smallest DFA that accepts $n$-copy has $2^{\Omega(n)}$ states.

Similarly, if we restrict ourselves to a binary stack alphabet, then I suspect that the smallest PDA that accepts $n$-copy has exponentially many states.

P.S. Feel free to send me an email if you would like to discuss further. :)


---

### Answer by username_3 on 2014-11-12. Score: 6

Let me second Michael's judgment, this is indeed an interesting
question. Michael's main idea can be combined with a result from the literature, thus providing a similar lower bound with a rigorous proof.

I will refer to bounds on CFG size in terms of the total number of alphabetic symbols in the $n$ regular expressions. Let this number be denoted by $k$. (As john\_leo noted, we will not find any useful bounds in terms of the number of regular expressions taking part in the intersection.)

Neither the OP nor Michael did find it necessary to mention this, but
an upper bound of $2^{k+1}$ (on the number of states) for converting
an intersection of regular expressions into a NFA can be easily
proved. For the record, here it is: Convert the regular expressions
into Glushkov automata, which are all non-returning. Then apply the
product construction to obtain an NFA for the intersection of these
languages. (I suppose that one can improve the bound to $2^k+1$ or
so.) An $s$-state NFA can be converted into a right-linear grammar
(which is a special case of a CFG) of size $O(s^2)$ (if we measure
grammar size as total number of symbols on the left- and
right-hand-sides of the productions), thus giving size $O(4^{k})$.
This bound of course sounds horrible if you have practical
applications in mind. Trying to prove a better bound using nondeterministic
transition complexity instead of nondeterministic state complexity for
estimating the size of the NFA may be worth the effort.

The other part is finding a witness language that can be succinctly expressed as the intersection of regular expressions, but is necessarily cumbersome to describe with a CFG. (Here we need to establish a lower bound on the size of all CFGs generating the language, of which there can be infinitely many.)
The following argument gives a $2^{\Omega(\sqrt{k}/\log k)}$ lower bound.

Consider the finite language $L\_n = \{\,ww^Rw \in \{a,b\}^\*\mid |w|=n\,\}$, where $w^R$ denotes the reversal of $w$. Then $L\_n$ can be expressed as the intersection of the following $2n+1$ regular expressions:

* $r\_i = (a+b)^ia(a+b)^{2(n-i-1)}a(a+b)^\*+(a+b)^ib(a+b)^{2(n-i-1)}b(a+b)^\*$, for $1\le i \le n$;
* $s\_i = (a+b)^\*a(a+b)^{2(n-i-1)}a(a+b)^i+(a+b)^\*b(a+b)^{2(n-i-1)}b(a+b)^i$, for $1\le i \le n$;
* $\ell = (a+b)^{3n}$

The total number $k$ of alphabetic symbols in this intersection of expressions is in $O(n^2)$.

Using an argument given in the proof of Theorem 13 in ([1](http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2304)), one can prove that every acyclic CFG that generates $L\_n$ must have at least $2^n/(2n) = 2^{\Omega(\sqrt{k}/\log k)}$ distinct variables, if the right-hand side of each rule has length at most $2$. The latter condition is necessary for arguing about the number of variables, since we can generate a finite language with a single variable. But from the perspective of grammar size, this condition is not really a restriction, since we can transform a CFG into this form with only a linear blowup in size, see ([2](http://www.informatica-didactica.de/cmsmadesimple/uploads/Artikel/LangeLeiss2009/LangeLeiss2009.pdf)). Notice that the language used by Arvind et al. is over an alphabet of size $n$, and this yields a bound of $n^n/(2n)$; but the argument carries over with obvious modifications.

Still, a large gap remains between $O(4^n)$ and the abovementioned lower bound.

**References:**

* V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan. [Arithmetic Circuits and the Hadamard Product of Polynomials](http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2304), FSTTCS 2009, Vol. 4 of LIPIcs, pp. 25-36
* Lange, Martin; Leiß, Hans (2009). "[To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm](http://www.informatica-didactica.de/cmsmadesimple/uploads/Artikel/LangeLeiss2009/LangeLeiss2009.pdf)". Informatica Didactica 8.


---

### Answer by username_4 on 2014-11-11. Score: 6

I don't think that there can be any non-trivial lower or upper bounds.  
For lower bounds, consider the language $L\_1 = \{ a^{2^k} \}$ for a fixed $k$. The size of the smallest context-free grammar is logarithmic in the size of $L\_1$'s regular expression, whereas the size of the smallest automaton for $L\_1$ is linear in the size of $L\_1$'s regex. This exponential difference stays the same if we intersect $L\_1$ with other such languages.  
For upper bounds, consider a language $L\_2$ that consists of exactly one [deBruijn-Sequence](http://en.wikipedia.org/wiki/De_Bruijn_sequence) of length $n$. It is known that the size of a smallest grammar for $L\_2$ is worst-case, i.e. $O\left( \frac{n}{\log n} \right)$, so the difference to the "smallest" automaton for $L\_2$ is simply a logarithmic factor, proposition 1 in

* D. Hucke, M. Lohrey, E. Noeth [Constructing Small Tree Grammars and Small Circuits for Formulas](http://arxiv.org/abs/1407.4286), to appear in FSTTCS 2014

A non-trivial general lower or upper bound would contradict those results, since what is true for the intersection of $n$ languages must be true for the intersection of $1$ language.

> **Comments:**
> **username_2**: The remark on the size of the smallest grammar for the single deBruijn-Sequence is quite interesting.  Could you please provide a reference.  Thank you.  
> **username_2**: Also, I could be mistaken, but it seems that you only addressed the problem for a single regular expression (rather than a product of regular expressions)?  
> **username_4**: @MichaelWehar Yep, I only considered one single regular expression. Because if it should be true for the intersection of $n$ languages, then it certainly must be true for the trivial intersection. I don't know how to reformulate the question to exclude these cases. I added the reference, should have done that right away, sorry.  
> **username_2**: Thank you!  You were able to describe a specific example.  Here is a simple remark that leads to the existence of such examples.  Let n be given.  There are 2^n strings of length n.  Also, there are no more than 2^n Turing machines with at most n/log(n) states.  Therefore, some string x of length n such that no Turing machine with fewer than n/log(n) states accepts the language {x}.  Therefore, {x} is accepted by a DFA with n states and cannot be accepted by a PDA with fewer than n/log(n) states.  

---

