Eine kontextfreie Grammatik ´G = (N, T, P, S)´ heißt linear, wenn alle Regeln aus P die Form ´A -> w_1Bw_2´ oder ´A -> w´ mit ´A, B in N´ und ´w_1, w_2, w in T^(**)´ haben. In einer Übungsaufgabe wurde bereits gezeigt, dass es für lineare Grammatiken eine Normalform gibt, bei der alle Regeln von der Form ´A -> aB´ oder ´A -> Ba´ oder ´A -> a´ oder ´A -> lambda´ mit ´A, B in N´ und ´a in T´ sind. Eine Sprache ´L´ heißt linear, wenn es eine lineare Grammatik ´G´ mit ´L(G) = L´ gibt.

Für lineare Sprachen gilt der folgende Schleifensatz:

Für jede lineare Sprache ´L´ gibt es eine Konstante ´k´ derart, dass für jedes Wort ´z in L´ mit ´|z| >= k´ eine Zerlegung ´z = uvwxy´ so existiert, dass folgendes gilt:

  1. ´|uvxy| <= k´
  2. ´|vx| >= 1´ (d.h. ´vx != lambda´)
  3. ´uv^iwx^iy in L´ für ´i >= 0´

Beweise, dass die Sprache ´L = {a^n b^n a^m b^m | n >= 1, m >= 1}´ eine kontextfreie Sprache, aber keine lineare Sprache ist.

Solution

  • Die kontextfreie Grammatik ´G = ({S,A}, {a,b}, {S -> "AA", A -> aAb, A -> ab}, S)´ erzeugt ´L´, denn von ´A´ startend wird ´{a^s b^s | s >= 1}´ erzeugt, und im ersten Schritt werden zwei ´A´ erzeugt. Wir nehmen an, dass ´L´ eine lineare Sprache ist. Dann gibt es nach dem Schleifensatz für lineare Sprachen eine Konstante ´k´ und für jedes Wort ´z in L´ mit ´|z| >= k´ eine Zerlegung ´z = uvwxy´ mit ´|uvxy| <= k´, ´vx != lambda´ und ´uv^iwx^iy in L´ für ´i >= 0´. Wir wählen ´z = a^(2k) b^(2k) a^(2k) b^(2k) in L´. Wegen ´|uvxy| <= k´, enthalten ´u´ und ´v´ nur den Buchstaben ´a´ und ´x´ und ´y´ nur den Buchstaben ´b´. Damit gilt ´u = a^p´, ´v = a^q´, ´x = b^t´, ´y = b^r´ mit ´p, q, t, r >= 0´ und ´q >= 1´ oder ´t >= 1´ (wegen ´vx != lambda´) und ´w = a^(2k-p-q) b^2^k a^(2k)b^(2k-r-t)´. Somit ergibt sich für ´i = 2´ das Wort

    ´uv^2wx^2y = a^p a^q a^q a^(2k−p−q) b^(2^k) a^(2k) b^(2k−r−t) b^t b^t b^r = a^(2k+p) b^(2k) a^(2k) b^(2k+t)´,

    das aber wegen ´q >= 1´ oder ´t >= 1´ nicht in ´L´ liegt. Damit haben wir einen Widerspruch zu der dritten Bedingung des Schleifensatzes.

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Proof
  • Duration: 40min
  • Credits: 5
  • Difficulty: 0.8
  • Tags: hpi context-free language
  • Note:
    HPI, 2014-05-07, Theoretische Informatik 2, Blatt 5, Aufgabe 1
  • Created By: adius
  • Created At:
    2014-07-22 14:08:20 UTC
  • Last Modified:
    2014-07-22 14:12:38 UTC