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$?
-
$\begingroup$ ??? 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. $\endgroup$– vznJul 6, 2014 at 0:14
-
$\begingroup$ @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. $\endgroup$– MaxJul 6, 2014 at 8:24
-
$\begingroup$ 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. $\endgroup$– vznJul 6, 2014 at 15:30
-
$\begingroup$ @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)$. $\endgroup$– MaxJul 6, 2014 at 16:03
-
$\begingroup$ Dyck languages 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. $\endgroup$– vznJul 6, 2014 at 16:13
3 Answers
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. :)
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.
-
$\begingroup$ 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. $\endgroup$ Nov 12, 2014 at 1:27
-
$\begingroup$ 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)? $\endgroup$ Nov 12, 2014 at 1:30
-
1$\begingroup$ @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. $\endgroup$– john_leoNov 12, 2014 at 9:35
-
1$\begingroup$ 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. $\endgroup$ Nov 14, 2014 at 0:45
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.