Mit Induktion beweisen, dass der Algorithmus auf Eingabe von w ∈ Σ* die Menge {A∈V | A => w} zurückgibt.

Question

Hallo, ich würde mich wirklich freuen wenn mir jemand hier helfen könnte:) Hier ist ein rekursiver Algorithmus (CYK) für das Wortproblem einer kontextfreien Grammatik G = (V, Σ, P, S) in Chomsky-Normalform.

Die Aufgabe: ich soll mithilfe von Induktion beweisen, dass der Algorithmus auf Eingabe von w ∈ Σ* die Menge {A∈V | A => w} zurück gibt.

function CYK (a1 . . . an ∈ Σ∗) ⊆ V ;
 const
      G = (V, Σ, P, S)      (Typ- 2 Grammatik in Chomsky-N.)
 global
      cache : dictionary ;  (Schlüssel: Wörter aus Σ∗, Werte: Teilmengen von V)
 var
      result , left , right ⊆ V ;
 begin
      if cache . containsKey (a1 . . . an ) then
        return cache [a1 . . . an ];

    if n = 1 then
        result ← {A ∈ V | A → an ∈ P};
    else
        result ← ∅;
        for i := 1 to n - 1 do
              left ← CYK (a1 . . . ai );
              right ← CYK (ai+1 . . . an );
              result ← result ∪ {A | A → BC ∈ P, B ∈ left, C ∈ right}
        od ;
    fi ;

    cache [a1 . . . an ] ← result ;
    return result ;
 end ;

Answer 1

Du gehst dabei genau wie nach dem klassischen Induktionsalgorithmus vor, d. h.

- Induktionsanfang \(\mathcal{A}(n_0)\)

- Induktionsvoraussetzung \(\mathcal{A}(n)\)

- Induktionsbehauptung \(\mathcal{A}(n+1)\)

- Induktionsschritt \(\mathcal{A}(n)\Longrightarrow\mathcal{A}(n+1)\)

Die Induktionsvariable ist dabei die Wortlänge n. Wähle für den Induktionsanfang \(n=1\) und spiele den Algorithmus einmal durch. Im Induktionsschritt gehst Du dann von einem Wort der Länge \(n+1\) aus.