Ist das Komplement von {ww | ...} kontextfrei?

13

Definieren Sie die Sprache als . Mit anderen Worten enthält die Wörter, die nicht als ein Wort ausgedrückt werden können, das zweimal wiederholt wird. Ist kontextfrei oder nicht?LLL={a,b}{www{a,b}}L={a,b}{www{a,b}}LLLL

Ich habe versucht, mit zu schneiden , aber ich kann immer noch nichts beweisen. Ich habe mir auch Parikhs Theorem angesehen, aber es hilft nicht.LLabababab

Evgeny Eltishev
quelle
Beachten Sie diese eng verwandte Frage .
Raphael

Antworten:

27

Es ist kontextfrei. Hier ist die Grammatik:

S A | B | A B | B A SA|B|AB|BA
A a | a A a | a A b | b A b | b A aAa|aAa|aAb|bAb|bAa
Bb|aBa|aBb|bBb|bBaBb|aBa|aBb|bBb|bBa

AA erzeugt Wörter ungerader Länge mit einema in der Mitte. Gleiches gilt für BB und bb .

Ich werde einen Beweis vorlegen, dass diese Grammatik korrekt ist. Let L = { a , b } *{ w w | w { a , b } * } (die Sprache , in der Frage).L={a,b}{www{a,b}}

Satz. L = L ( S ) . Mit anderen Worten, diese Grammatik erzeugt die Sprache in der Frage.L=L(S)

Beweis. Dies gilt sicherlich für alle ungeraden Länge Worten, da diese Grammatik alle ungeraden Längen Worte erzeugt, ebenso wie L . Konzentrieren wir uns also auf gerade Wörter.L

Angenommen, x L hat eine gerade Länge. Ich zeige das x L ( G ) . Insbesondere behaupte ich, dass x in der Form x = u v geschrieben werden kann , wobei sowohl u als auch v eine ungerade Länge und unterschiedliche zentrale Buchstaben haben. Somit x kann von beiden abgeleitet werden A B oder B A (je nachdem, ob u ‚s zentraler Buchstabe ist a oder b ). Anspruchsberechtigung: Es sei der i- te Buchstabe von xxLxL(G)xx=uvuvxABBAuabixmit x i bezeichnet werden , so dass x = x 1 x 2x n . Dann, da x nicht in { w w w { a , b } n / 2 } ist , muss ein Index i existieren, so dass x ix i + n / 2 ist . Folglich können wir u = x 1x 2 i nehmen -xix=x1x2xnx{www{a,b}n/2}ixixi+n/21 undv= x 2 i x n ; der zentrale Buchstabe vonuist x i und der zentrale Buchstabe vonvist x i + n / 2 , also habenu,vdurch Konstruktionunterschiedliche zentrale Buchstaben.u=x1x2i1v=x2ixnuxivxi+n/2u,v

Nehmen wir als nächstes an, dass x L ( G ) gerade Länge hat. Ich werde zeigen, dass wir x L haben müssen . Wenn x sogar Länge hat, muss es von beiden ableitbar sein A B oder B A ; ohne Beschränkung der Allgemeinheit an , dass es von ableitbar ist , A B , und x = u v wobei U ableitbar aus ist , A und v ist ableitbar von B . Wenn u , v die gleichen Längen haben, müssen wir u ≠ habenxL(G)xLxABBAABx=uvuAvBu,vv (da sie verschiedene zentrale Buchstaben haben), so x { w w | w { a , b } * } . Nehmen wir also an , dass u , v unterschiedliche Längen haben, z. B. Länge und n - . Dann sind ihre zentralen Buchstaben u ( + 1 ) / 2 und v ( n - + 1 ) / 2 . Die Tatsachedass Uuvx{www{a,b}}u,v,v have different central letters means that u(+1)/2v(n+1)/2. Since x=uv, this means that x(+1)/2x(n++1)/2. If we attempt to decompose x as x=ww where w,w have the same length, then we'll discover that w(+1)/2=x(+1)/2x(n++1)/2=w(+1)/2, i.e., ww, so x{www { a , b } } . Insbesondere folgt, dass x L ist .

Evgeny Eltishev
quelle
2
Ich habe die Antwort bearbeitet, um einen Beweis für die Richtigkeit dieser Grammatik zu liefern, basierend auf dem Hinweis / der Skizze von Evgeny Eltishev. Hoffentlich sollte jetzt klarer werden, warum dies funktioniert.
DW
Can it generate "aabb" ?
manasij7479
1
@manasij7479 Yes: SABaBa(aBb)aabb.
J.-E. Pin
3

This language is context free it was proved in the following paper:

Tomaszewski, Zach. "A Context-Free Grammar for a Repeated String." Journal of Information and Computer Science, 2012 (PDF).

The grammar is as follows: SEUϵEABBAAZAZaBZBZbUZUZZZab

A. Mashreghi
quelle
8
Welcome! The following is not a criticism of this answer. The Journal of Information and Computer Science is published by "World Academic Union", which is on Beall's list of predatory open access publishers. It's sad that there are companies in the world who will take relatively large amounts of people's money to publish papers that do nothing more than solve undergraduate-level exercises.
David Richerby
I don't have enough reputation to comment on the above answer. But that grammar seems wrong to me. It cannot generate "aaab" which is in the language.
A. Mashreghi
1
After performing CFGCNFCYK (you should try it), SABaAaBaaaBaaab, so it seems it can generate aaab.
Evil
You right it does
A. Mashreghi