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?L
Ich habe versucht, mit zu schneiden , aber ich kann immer noch nichts beweisen. Ich habe mir auch Parikhs Theorem angesehen, aber es hilft nicht.L
formal-languages
context-free
formal-grammars
Evgeny Eltishev
quelle
quelle
Antworten:
Es ist kontextfrei. Hier ist die Grammatik:
S→A|B|AB|BA
A→a|aAa|aAb|bAb|bAa
B→b|aBa|aBb|bBb|bBa
S → A | B | A B | B A
A → a | a A a | a A b | b A b | b A a
B→b|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}∗∖{ww∣w∈{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 xx∈L x∈L(G) x x=uv u v x AB BA u a b i x mit x i bezeichnet werden , so dass x = x 1 x 2 ≤ x n . Dann, da x nicht in { w w ∣ w ∈ { a , b } n / 2 } ist , muss ein Index i existieren, so dass x i ≠ x i + n / 2 ist . Folglich können wir u = x 1 ⋯ x 2 i nehmen -xi x=x1x2⋯xn x {ww∣w∈{a,b}n/2} i xi≠xi+n/2 1 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=x1⋯x2i−1 v=x2i⋯xn u xi v xi+n/2 u,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 ≠ habenx∈L(G) x∈L x AB BA AB x=uv u A v B u,v v (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 Uu≠v x∉{ww∣w∈{a,b}∗} u,v ,v have different central letters means that u(ℓ+1)/2≠v(n−ℓ+1)/2. Since x=uv, this means that x(ℓ+1)/2≠x(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)/2≠x(n+ℓ+1)/2=w′(ℓ+1)/2, i.e., w≠w′, so x∉{ww∣ w ∈ { a , b } ∗ } . Insbesondere folgt, dass x ≤ L ist .
quelle
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: S→E∣U∣ϵE→AB∣BAA→ZAZ∣aB→ZBZ∣bU→ZUZ∣ZZ→a∣b
quelle