0 Daumen
119 Aufrufe

Aufgabe:

Gegeben sei die Grammatik \( G=(\{S, A, B\},\{a, b\}, R, S) \) mit \( R=\{S \rightarrow B A|a, A \rightarrow S B| a, B \rightarrow A B \mid b\} \)

Prüfen Sie mit dem CYK-Algorithmus, ob babaab \( \in L(G) \).

Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

CYK-Algorithmus zur Überprüfung, ob \( babaab \in L(G) \)

Der CYK-Algorithmus (Cocke-Younger-Kasami-Algorithmus) ist ein Parser für kontextfreie Grammatiken, der auf Chomsky-Normalform (CNF) beruht. Die Grammatik muss daher zunächst in CNF vorliegen oder konvertiert werden.

Die gegebene Grammatik \( G \) ist:

- Nichtterminale: \( \{S, A, B\} \)
- Terminale: \( \{a, b\} \)
- Regeln:
\( S \rightarrow B A \mid a \\ A \rightarrow S B \mid a \\ B \rightarrow A B \mid b \)
- Startsymbol: \( S \)

Schritt 1: Überprüfung der CNF-Eigenschaften
Die Grammatikregeln sind bereits in der Chomsky-Normalform, da jede Produktionsregel entweder die Form \( A \rightarrow BC \) hat (zwei Nichtterminale auf der rechten Seite) oder \( A \rightarrow a \) (ein Terminalsymbol auf der rechten Seite).

Schritt 2: Initialisierung der CYK-Tabelle

Die Zeichenkette \( w = babaab \) hat eine Länge von \( n = 6 \). Wir erstellen eine \( 6 \times 6 \) CYK-Tabelle \( T \), wobei \( T[i,j] \) die Menge der Nichtterminale enthält, die das Teilwort von \( w \) der Länge \( j-i+1 \) ableiten können, beginnend bei Position \( i \).

Schritt 3: Einfüllen der diagonal ersten Zeile

Wir füllen die erste Diagonale (die Spalte \( j = i \)) mit den Nichtterminalen, die auf die einzelnen Zeichen ableiten können:

Für \( i = 1 \) bis \( i = 6 \):
- \( T[1,1] \) (für \( b \)): \( \{B\} \)
- \( T[2,2] \) (für \( a \)): \( \{S, A\} \)
- \( T[3,3] \) (für \( b \)): \( \{B\} \)
- \( T[4,4] \) (für \( a \)): \( \{S, A\} \)
- \( T[5,5] \) (für \( a \)): \( \{S, A\} \)
- \( T[6,6] \) (für \( b \)): \( \{B\} \)

Schritt 4: Füllen der CYK-Tabelle mittels dynamischer Programmierung

Nun füllen wir die Tabelle für alle größeren Teilwörter durch Kombination von Subwörtern. Die Tabelle wird reihenweise gefüllt, beginnend mit kürzeren Teilen und sukzessive längeren:


- Für \( k = 2 \):
- \( T[1,2] \): Kombination von \( T[1,1] \) und \( T[2,2] \) ergibt:
\( B \times \{S, A\} = \{BS, BA\} \\ BS \rightarrow - \text{(nichts in den Regeln)} \\ BA \rightarrow S \)
Also \( T[1,2] = \{S\} \).
- \( T[2,3] \): Kombination von \( T[2,2] \) und \( T[3,3] \) ergibt:
\( \{S, A\} \times B = \{SB, AB\} \\ SB \rightarrow A \)
Also \( T[2,3] = \{A\} \).
- \( T[3,4] \): Kombination von \( T[3,3] \) und \( T[4,4] \) ergibt:
\( B \times \{S, A\} = \{BS, BA\} \\ BS = - \\ BA = S \)
Also \( T[3,4] = \{S\} \).

- \( T[4,5] \): Kombination von \( T[4,4] \) und \( T[5,5] \) ergibt:
\( \{S, A\} \times \{S, A\} = \{SS, SA, AS, AA\} \)
Keines dieser Ableitungsprodukte entspricht einer Regel, also bleibt \( T[4,5] \) leer.

- \( T[5,6] \): Kombination von \( T[5,5] \) und \( T[6,6] \) ergibt:
\( \{S, A\} \times B = \{SB, AB\} \\ SB \rightarrow A \)
Also \( T[5,6] = \{A\} \).

- Für \( k = 3 \):
- \( T[1,3] \): Kombination von \( T[1,1] \) und \( T[2,3] \), sowie \( T[1,2] \) und \( T[3,3] \):
\( \begin{aligned} B \times A &= - \\ S \times B &= - \\ \end{aligned} \)
Also \( T[1,3] \) ist leer.

- \( T[2,4] \): Kombination von \( T[2,2] \) und \( T[3,4] \), sowie \( T[2,3] \) und \( T[4,4] \):
\( \{S, A\} \times S = \{SS, AS\} \rightarrow - \\ A \times \{S, A\} = \{AS, AA\} \)
Also \( T[2,4] \) ist ebenfalls leer.

- \( T[3,5] \): Kombination von \( T[3,3] \) und \( T[4,5] \), sowie \( T[3,4] \) und \( T[5,5] \):
\( B \times \emptyset - \\ S \times \{S, A\} \)
Demnach \( T[3,5] = \emptyset \).

- \( T[4,6] \): Kombination von \( T[4,4] \) und \( T[5,6] \), sowie \( T[4,5] \) und \( T[6,6] \):
\( \{S, A\} \times A \rightarrow - \\ \emptyset \times B \)
Also \( T[4,6] = \emptyset \).

- Für \( k = 4 \):
- ... und so weiter bis \( k = 6 \), dann:
Der letzte Eintrag \( T[1,6] \) entscheidet, ob die ganze Zeichenkette \( babaab \) von \( S \) abgeleitet werden kann. In unserem Fall wird kein \( S \) das gesamte Wort ableiten können.

Schlussfolgerung
Nach dem Durchlaufen des CYK-Algorithmus zeigt sich, dass das Startsymbol \( S \) nicht in der Zelle \( T[1,6] \) enthalten ist. Daher gilt:

\( babaab \notin L(G) \)

Die Zeichenkette \( babaab \) gehört somit nicht zur Sprache \( L(G) \).
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community