Ist die Sprache { } kontextfrei oder nicht?
Mir wurde klar, dass ich fast alle Varianten dieser Frage mit unterschiedlichen Bedingungen über die Beziehung zwischen i, j und k kennengelernt habe, aber nicht diese.
Ich vermute, dass es nicht kontextfrei ist, aber haben Sie einen Beweis?
Antworten:
Ogdens Lemma sollte funktionieren:
Für ein gegebenes wähle und markiere alle (und sonst nichts).a i b p c k bp einichbpck b
k b b i kich und werden so gewählt, dass es für jede Wahl, wie viele tatsächlich gepumpt werden, einen Pumpexponenten gibt, so dass die Anzahl von gleich und einer, bei dem es gleich .k b b ich k
Das heißt, und müssen aus der Menge .k ⋂ 1 ≤ n ≤ p { p - n + m * n | m ∈ N 0 }ich k ⋂1≤n≤p{p−n+m∗n∣m∈N0}
Ich bin mir ziemlich sicher, aber zu faul, um formal zu beweisen, dass dieses Set unendlich ist.
quelle
Wenn die Beziehung zwischen den drei Einschränkungen "ODER" ist, ist die Sprache CFL. Die Lösung nutzt die Tatsache, dass CFLs unter Union geschlossen sind. Offensichtlich sind die folgenden CFLs: , L 2 = { a i b j c k | i ≠ k , j ≥ 0 } , L 3 = { a i bL1={aibjck∣i≠j, k≥0} L2={aibjck∣i≠k, j≥0}
(wenn man nicht überzeugt, kann man auf aussehen L i als Verkettung von CFL und regelmäßiger Sprache zum Beispiel. L 1 ist { a i b j | i ≠ j } verketteten zu { c } ∗ .L3={aibjck∣j≠k, i≥0} Li L1 {aibj∣i≠j} {c}∗
Die gewünschte Sprache ist die Vereinigung der obigen . Es ist also CFL.L=L1∪L2∪L3
quelle