Geben Sie für folgende Sprache eine kontextsensitive Grammatik an.

Question

Hallo,

Ich habe eine Aufgabe gestellt bekommen, die ich nicht ganz verstehe. Könnte mir vielleicht jemand dabei helfen?

Wir betrachten “fast” korrekt geklammerte Wörter. Ein Wort w uber Σ = {(, ), [, ]} ist “fast” korrekt geklammert, wenn die beiden Wörter w_1 und w_2, welche durch Entfernen von allen Klammern ( und ) bzw. allen Klammern [ und ] aus w entstehen, korrekt geklammert sind.
Zum Beispiel ist ([)[]] fast korrekt geklammert, da sowohl w_1 = [[]] als auch w_2 = () korrekt geklammert sind.

a) Geben Sie für die Sprache aller fast korrekt geklammerten Wörter eine kontextsensitive Grammatik an.

b) Beweisen Sie, dass eben diese Sprache nicht kontextfrei ist.

Ich bedanke mich im Voraus für alle Antworten und Hilfestellungen!

Answer 1

a)

    \(\begin{aligned} S & \to T\\ T & \to(T)T\,|\,[T]T\,|\,\varepsilon \end{aligned}\)

Überlege dir, welche Produktionsregeln du noch für \((T)T\) und \([T]T\) benötigst.

b) Pumpinglemma für kontextfreie Sprachen.

Comments

Das ist mein Ansatz:

Terminale:

(
)
[
]
a (beliebiger Buchstabe aus einem Alphabet Σ)

Nicht-Terminale:

S (Startsymbol)
A (für Wörter, die nur Klammern enthalten)
B (für Wörter, die nur Buchstaben enthalten)
C (für Wörter, die sowohl Klammern als auch Buchstaben enthalten)

Die Grammatikregeln lauten wie folgt:

S → ε
S → A
S → B
S → C
A → ε
A → (A)
A → [A]
A → (B)
A → [B]
B → aB
B → ε
C → (C)B
C → [C]B
C → (B)C
C → [B]C

Ist die Grammatik aber richtig?

---

b) Beweisen Sie, dass eben diese Sprache nicht kontextfrei ist.

Die Aufgabenstellung legt die Vermutung nahe, dass die Sprache nicht kontextfrei ist.

Du hast aber eine kontextfreie Grammatik angegeben.

S → B
B → aB
B → ε

Damit kann das Wort [ abgeleitet werden.

Das Wort [ ist aber kein fast korrekt geklammertes Wort.

---

meine Lösung wäre:

S -> (A) | [B] | AB | BC
A -> (A)A | ε
B -> [B]B | ε
C -> (C) | [C] | ε

---

Die Aufgabenstellung legt die Vermutung nahe, dass die Sprache nicht kontextfrei ist.

Du hast aber eine kontextfreie Grammatik angegeben.

Das Wort ([)] ist fast korrekt geklammert, kann aber mit deiner Grammatik nicht abgeleitet werden.

---

Welche Produktionsregeln fehlen noch?

---

Produktionsregeln, die dafür sorgen, dass nicht nur korrekt geklammerte Ausdrücke abgeleitet werden, sondern auch fast korrekt geklammerte Ausdrücke.

Verwende \((T)T\) und \([T]T\) als linke Seiten solcher Regeln.

---

komme bei der Aufgabe leider nicht weiter...