Complexity of intersection of regular languages as context-free grammars

Question

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$?

Answer 1

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

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 2

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 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, 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.

Answer 3

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), 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). 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, 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". Informatica Didactica 8.