Gibt es eine CFG mit Polynomgröße, die diese endliche Sprache beschreibt?

9

Gibt es Permutationen und Polynomgröße (in ) kontextfreie Grammatik, die die endliche Sprache über Alphabet ?| w | = n { w π 1 ( w ) π 2 ( w ) } { 0 , 1 }π1,π2|w|=n{wπ1(w)π2(w)}{0,1}

UPDATE: Für eine Permutation es möglich. ist die Umkehrung oder relativ geringfügige Modifikation der Umkehrung.πππ

jerr18
quelle
5
Auch auf math.stackexchange gefragt. Was er meint ist: Gibt es eine Folge von Permutationen π1n,π2nSn so dass die Sprachen haben CFGs mit Polynomgröße? Ln={wπ1(w)π2(w):w{0,1}n}
Yuval Filmus
1
Wissen wir, ob es ein CFG für L=nLn ?
Kaveh
4
@Kaveh: Die Antwort ist nein, für jede Folge von Dauerwellen. Wenn Ihre Sprache kontextfrei wäre, hätte sie eine Pumplänge p . Wenden Sie das Pump-Lemma für CFGs auf die Zeichenfolge in L an, die w = 0 p 1 p zugeordnet ist . Das Pump-Lemma für CFGs lässt uns auch sagen, dass, wenn der OQ eine positive Antwort hat, das CFG für L n mindestens Ω ( n / log n ) Variablen verwenden muss, da wir 3 n benötigen , um kleiner als die Pumplänge zu sein , so dass unser CFG für L n keine Zeichenfolgen mit einer Länge > 3 akzeptiertLpw=0p1pLnΩ(n/logn)3nLn . Ich sehe noch nicht ein, wie ich damit eine positive Antwort auf den OQ ausschließen kann, aber es könnte möglich sein. >3n
Joshua Grochow
1
@Kaveh: (Auch wenn die Reihenfolge der Dauerwellen willkürlich gewählt werden kann, muss Ihre Sprache nicht einmal berechenbar sein ... Der OQ scheint von Natur aus ungleichmäßig zu sein.)L
Joshua Grochow

Antworten:

13

Chomsky Normalform

Ein CFG liegt in CNF (Chomsky-Normalform) vor, wenn die einzigen Produktionen die Form und A B C haben ; Eine Grammatik kann mit nur quadratischer Vergrößerung zu CNF gebracht werden.AaABC

Für eine Grammatik in CNF haben wir das schöne Unterwort Lemma: Wenn G ein Wort w erzeugt , gibt es für jedes w ein Unterwort x von w der Länge / 2 | x | < ℓ, das von einem Nicht-Terminal von G erzeugt wird . Beweis: Steigen Sie vom (binären) Syntaxbaum ab und gehen Sie immer zu dem Kind, das das längere Unterwort generiert. Wenn Sie mit einem Teilwort der Größe zumindest begonnen l , können Sie nicht haben unten gegangen l / 2 .GGwwxw/2|x|<G/2

Lösung

Ohne Verlust der Allgemeinheit können wir annehmen, dass eine Grammatik für (eine solche Sprache mit spezifischem π 1 , π 2S n ) in Chomsky-Normalform vorliegt. Die Sprache L n besteht aus den Wörtern w ( x ) = x π 1 ( x ) π 2 ( x ) für alle x { 0 , 1 } n .Lnπ1,π2SnLnw(x)=xπ1(x)π2(x)x{0,1}}n

Mit dem Unterwort Lemma können wir für jedes einen Teilstring s ( x ) der Länge n findenw(x)s(x)wird durch ein SymbolA(x) erzeugtund tritt an der Positionp(x) auf.

n2|s(x)|<n
A(x)p(x)

Angenommen, und A ( x ) = A ( y ) . Da | s ( x ) | < n kann das Unterwort s ( x ) nicht sowohl den x- Teil als auch den π 2 ( x ) -Teil von w ( x ) schneiden ; wir können annehmen, dass es vom x- Teil getrennt ist. Also wp(x)=p(y)A(x)=A(y)|s(x)|<ns(x)xπ2(x)w(x)x hat die Form x α s ( x ) β . Dies impliziert, dass A ( x ) genau eine Zeichenfolge erzeugt, nämlich s ( x ) . Daher ist s ( x ) = s ( y ) .w(x)xαs(x)βA(x)s(x)s(x)=s(y)

Jetzt schneidet entweder π 1 ( y ) oder π 2 ( y ) an mindestens n / 4 Stellen und bestimmt somit mindestens n / 4 Bits von y . Daher höchstens 2 3 n / 4 Strings y { 0 , 1 } n haben kann p ( x ) = p ( y )s(y)π1(y)π2(y)n/4n/4y23n/4y{0,1}np(x)=p(y)und . Da es für p ( y ) höchstens 3 n Möglichkeiten gibt, erhalten wir mindestens 2 n / 4A(x)=A(y)3np(y) verschiedene Nicht-Terminals in der Grammatik.

2n/43n

Kommentar: Der gleiche Beweis funktioniert, wenn , dh beliebige Permutationen auf der Menge aller n- Bit-Wörter sind. Bei n / 4 Bits von π i ( y ) gibt es genau 2 3 n / 4 Vorbilder y .π1,π2S{0,1}nnn/4πi(y)23n/4y

Mehr Beispiele

Mit der gleichen Methode kann nachgewiesen werden, dass für die Sprache, in der jedes Zeichen genau zweimal vorkommt, ein CFG mit exponentieller Größe in der Größe des Alphabets erforderlich ist. Wir können "zweimal" durch eine andere Teilmenge von als vier triviale ersetzen (wobei 0 ignoriert wird und entweder keine von N 1 oder alles davon enthält).N0N1

Ich würde mich über eine Referenz für diese Beweismethode freuen.

Yuval Filmus
quelle
2
Yuval, könnten Sie bitte die Lösung auch hier kopieren.
Kaveh
Danke Yuval. Wenn Ihre Methode korrekt und neuartig ist, würde ich gerne einen Artikel lesen, in dem allgemeinere Fälle mit positiven oder negativen Ergebnissen zu polysize CFGs für endliche oder unendliche Sprachen untersucht werden.
18.
3
Es gibt diesen Artikel: cs.toronto.edu/~yuvalf/cfg.pdf .
Yuval Filmus
Ich nehme an, mit der Ausnahme meinen Sie "mindestens ein Auftreten von Terminal". Würde dies bedeuten, dass Sie alle Permutationen erzeugen können, indem Sie mit Σ | schneiden Σ | ? N.1Σ|Σ|
18.
1
Siehe verwandte Frage cstheory.stackexchange.com/q/5014, in der Yuval eine Antwort mit einer veröffentlichten Referenz gepostet hat.
András Salamon