Komplexität der Überschneidung regulärer Sprachen als kontextfreie Grammatik

Gibt es bei regulären Ausdrücken $R_1, \dots, R_n$ nicht-triviale Grenzen für die Größe der kleinsten kontextfreien Grammatik für $R_1 \cap \cdots \cap R_n$ ?

Das ist eine großartige Frage und liegt wirklich in meinem Interesse. Ich bin froh, dass du es Max gefragt hast.

Es seien DFAs mit jeweils höchstens O ( n ) Zuständen gegeben. Es wäre schön, wenn es einen PDA mit subexponentiell vielen Zuständen gäbe, der die Schnittmenge der DFA-Sprachen akzeptiert. Ich schlage jedoch vor, dass ein solcher PDA nicht immer existiert.$n$$O(n)$

Beachten Sie die Kopiersprache. Beschränken Sie sich jetzt auf das Kopieren von Zeichenfolgen der Länge n.

Man betrachte formal -copy : = { x $n$$:=$ .$\{ xx \, | \, x \in \{0,1\}^{n}\}$

Wir stellen -copy als Durchschnitt von n DFA der Größe höchstens O ( n ) . Der kleinste DFA, der n- Kopien akzeptiert, hat jedoch 2 Ω ( n ) Zustände.$n$$n$$O(n)$$n$$2^{\Omega(n)}$

Wenn wir uns auf ein binäres Stapelalphabet beschränken, vermute ich, dass der kleinste PDA, der Kopien akzeptiert, exponentiell viele Zustände hat.$n$

PS Sie können mir gerne eine E-Mail senden, wenn Sie weitere Fragen haben. :)

Ich glaube nicht, dass es irgendwelche nicht trivialen Unter- oder Obergrenzen geben kann.
Betrachten Sie für untere Schranken die Sprache für ein festes k . Die Größe der kleinsten kontextfreie Grammatik ist in der Größe von logarithmischer L 1 ‚s regulärer Ausdruck, während die Größe des kleinsten Automaten für L 1 linear in der Größe ist , L 1 ‘ s regex. Dieser exponentielle Unterschied bleibt gleich, wenn wir L 1 mit anderen solchen Sprachen schneiden . Betrachten Sie für obere Schranken eine Sprache L 2 , die aus genau einer besteht$L_1 = \{ a^{2^k} \}$$k$$L_1$$L_1$$L_1$$L_1$
$L_2$deBruijn-Sequenz der Länge . Es ist bekannt, dass die Größe einer kleinsten Grammatik für L 2 der schlechteste Fall ist, dh O ( $n$$L_2$, also ist die Differenz zum "kleinsten" Automaten fürL2einfach ein logarithmischer Faktor, Satz 1 in$O\left( \frac{n}{\log n} \right)$$L_2$

• D. Hucke, M. Lohrey, E. Noeth Konstruktion kleiner Baumgrammatiken und kleiner Schaltkreise für Formeln , erscheint in FSTTCS 2014

Eine nicht triviale allgemeine Unter- oder Obergrenze würde diesen Ergebnissen widersprechen, da das, was für den Schnittpunkt von Sprachen gilt, für den Schnittpunkt von 1 Sprache gilt.$n$$1$

Lassen Sie mich Michaels Urteil hinterfragen, das ist in der Tat eine interessante Frage. Michaels Hauptidee kann mit einem Ergebnis aus der Literatur kombiniert werden, wodurch eine ähnliche Untergrenze mit einem strengen Beweis versehen wird.

Ich beziehe mich auf die Grenzen der CFG-Größe in Bezug auf die Gesamtzahl der alphabetischen Symbole in den regulären Ausdrücken. Diese Zahl sei mit k bezeichnet . (Wie john_leo bemerkte, werden wir keine nützlichen Grenzen in Bezug auf die Anzahl der regulären Ausdrücke finden, die an der Schnittmenge teilnehmen.)$n$$k$

Weder das OP noch Michael hielten es für notwendig, dies zu erwähnen, aber eine Obergrenze von (für die Anzahl der Zustände) zur Umwandlung einer Schnittmenge regulärer Ausdrücke in eine NFA kann leicht bewiesen werden. Für die Aufzeichnung hier ist es: Konvertieren Sie die regulären Ausdrücke in Glushkov-Automaten, die alle nicht zurückkehren. Wenden Sie dann die Produktkonstruktion an, um eine NFA für die Schnittmenge dieser Sprachen zu erhalten. (Ich nehme an, dass man die Grenze auf 2 k + 1 oder so verbessern kann .) Ein s- Zustand-NFA kann in eine rechtslineare Grammatik (was ein Sonderfall einer CFG ist) der Größe O ( s 2$2^{k+1}$$2^k+1$$s$$O(s^2)$(Wenn wir die Grammatikgröße als Gesamtzahl der Symbole auf der linken und rechten Seite der Produktionen messen), ergibt sich Größe . Diese Grenze klingt natürlich schrecklich, wenn Sie praktische Anwendungen im Auge haben. Der Versuch, eine bessere Bindung unter Verwendung von nicht deterministischer Übergangskomplexität anstelle von nicht deterministischer Zustandskomplexität zur Schätzung der Größe der NFA zu beweisen, kann sich lohnen.$O(4^{k})$

Der andere Teil besteht darin, eine Zeugensprache zu finden, die sich prägnant als Schnittmenge regulärer Ausdrücke ausdrücken lässt, deren Beschreibung mit einer CFG jedoch mühsam ist. (Hier müssen wir eine Untergrenze für die Größe aller CFGs festlegen, die die Sprache erzeugen, von denen es unendlich viele geben kann.) Das folgende Argument ergibt Untergrenze.$2^{\Omega(\sqrt{k}/\log k)}$

Betrachte die endliche Sprache , wobei w R die Umkehrung von w bezeichnet . Dann kann L n als Schnittmenge der folgenden 2 n + 1 regulären Ausdrückeausgedrückt werden:$L_n = \{\,ww^Rw \in \{a,b\}^*\mid |w|=n\,\}$$w^R$$w$$L_n$$2n+1$

• $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)^*$$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$$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.