Kontextsensitive Grammatiken, Regel ohne Kontext

Question

Frage:

Wieso ist diese Regel:

A -> aBC

bei einer kontextsensitiven Grammatik erlaubt?

Kontextfrei ist sie, aber wieso kontextsensitiv? Der Kontext bleibt doch gar nicht erhalten, A verschwindet doch komplett und der Kontext bleibt nicht erhalten.

Wo ist mein Denkfehler?

Liebe Grüße

Comments

Und wieso ist die einzelne Regel

S -> aSa in einer kontextsensitiven Grammatik nicht erlaubt?

Es wäre doch nur nicht erlaubt, wenn es die Sonderregel S -> ε geben würde, dann dürfte S nicht in der Qonclusio sein. Aber das wissen wir ja gar nicht, ob es diese Sonderregel gibt.

Wieso ist Ca -> CbC bei einer kontextsensitiven Grammatik nicht erlaubt?

C bleibt erhalten, das a wird zu bC.

Answer 1

Wieso ist diese Regel:

A -> aBC

bei einer kontextsensitiven Grammatik erlaubt?

Eine kontextsensitive Grammatik mit Nichtterminalsymbolen aus \(\Gamma\) und Terminalsymbolen aus \(\Sigma\) darf Regeln der Form

        \(\alpha X\beta \to \alpha \gamma \beta\)

haben, wobei \(\alpha,\beta \in (\Gamma\cup\Sigma)^*\) sind. Weil \((\Gamma\cup\Sigma)^*\) das leere Wort enthält, folgt daraus insbesondere, dass \(\alpha\) und \(\beta\) leer sein dürfen. Das hätte man durch aufmerksames Lesen der Defintion herausfinden können.

Und wieso ist die einzelne Regel

S -> aSa in einer kontextsensitiven Grammatik nicht erlaubt?

Das Startsymbol darf nicht auf der rechten Seite von Regeln vorkommen. Auch das steht in der Definition.

Wieso ist Ca -> CbC bei einer kontextsensitiven Grammatik nicht erlaubt?

Terminalsymbole dürfen nicht ersetzt werden. Schau dir mal die Definition kontextsensitive Grammatik an.

Comments

Aber in der Definition von kontextsensitiven Grammatiken steht doch, dass S auf der rechten Seite nur nicht vorkommen darf, wenn es zusätzlich die Regel S -> ε gibt. Das weiß man ja hier gar nicht!

---

Oswald,

bei der Regel

Bc -> cBcc

die ist dann kontextsensitiv, weil sie zuerst auf der linken Seite für α, β das leere Wort enthält, und dann auf der rechten Seite, Bc erhalten bleibt, aber α, β = c werden, richtig?

---

\(\alpha X\beta \to \alpha \gamma \beta\)

In der Regel

        \(Bc \to cBcc\)

ist \(\alpha = \varepsilon\), \(X = B\), \(\beta = c\) und \(\gamma = Bc\).

---

Ahhh, danke dir!

---

auf der linken Seite für α, β das leere Wort enthält, ... aber α, β = c werden

Das wäre ungefähr so also ob du die Gleichung

        \(x + 4 = 3\cdot x\)

löst indem du auf der linken Seite für \(x\) den Wert 11 einsetzt und auf der rechten Seite für \(x\) den Wert 5 einsetzt.

---

Also die richtige Denkweise?

---

Warum ist S -> aAa bei einer kontextsensitiven Grammatik erlaubt?

α = ε, β = ε, X = S

geht über zu aAa.

α = a = β, aber γ = A ?

---

Hallo, Oswald, bitte, falls du Zeit hast, wäre es lieb, wenn du mir antworten würdest. Liebe Grüße

---

Aber in der Definition von kontextsensitiven Grammatiken steht doch, dass S auf der rechten Seite nur nicht vorkommen darf, wenn es zusätzlich die Regel S -> ε gibt.

Das steht unter wikipedia://Kontextsensitive_Grammatik anders.

weil sie zuerst auf der linken Seite für α, β das leere Wort enthäl

Dann sind \(\alpha\) und \(\beta\) auch auf der rechten Seite das leere Wort.

Warum ist S -> aAa bei einer kontextsensitiven Grammatik erlaubt?

\(\alpha = \beta = \varepsilon\), \(\gamma = aAa\). Beachte, dass \(\gamma\in (\Gamma\cup\Sigma)^*\) sein darf, und nicht nur aus \(\Gamma^*\) oder \(\Sigma^*\) oder gar \(\Gamma\) oder \(\Sigma\).

---

Aber was ist denn mit

S -> Bcc ?

α = β = ε

X = S

Laut Musterlösung erlaubt, "S wird ersetzt durch leeren Kontext". Was ist denn damit gemeint? γ = Bcc ?

Bei ABC -> AC steht auch, dass es NICHT erlaubt sei, da B durch das leere Wort ersetzt werden würde.

Aber es gilt doch: γ ∈ (Γ ∪ ∑)*

Und das * bedeutet doch, dass γ auch das leere Wort sein kann!

Bei uns steht im Skript zu kontextsensitiven Grammatiken:

"Das heißt, bei jeder Regelanwendung:
• Eine Variable A wird in einen String α mit |α| ≥ 1 überführt
• Die Ersetzung von A durch findet nur statt, wenn der in der Regel
geforderte Kontext (u und v) vorhanden ist
• Das Wort wird nicht kürzer, außer bei ε ∈ L. "

---

∀ (P-> Q) ∈ R:

1. ∃ u,v,α ∈ (V∪T)* ∃A ∈ V (P = uAv und Q = uαv mit |α| ≥ 1), oder die Regel hat die Form S -> ε

2. S nicht in Q

---

Oswald,

schau mal bitte hier diese Regel:

bBbB -> bbBbbB ist in einer kontextsensitiven Grammatik erlaubt. Wieso?

Das erste B wird durch bBb erstetzt, oder?

---

S -> Bcc ?

α = β = ε, X = S, γ = Bcc.

"S wird ersetzt durch leeren Kontext"

Variablen werden nicht durch Kontext ersetzt.

Aber es gilt doch: γ ∈ (Γ ∪ ∑)*

Genauer gesagt muss sogar γ ∈ (Γ ∪ ∑)⁺ sein.

bBbB -> bbBbbB ... Das erste B wird durch bBb erstetzt, oder?

Ja.

---

Oswald, du hast doch aber weiter oben kommentiert:

" Beachte, dass γ ∈ (Γ ∪ ∑ )* sein darf, ..."

Was stimmt denn nun? Ist das leere Wort enthalten, also *, oder ist es nicht enthalten (^+) ?

Liebe Grüße

---

Was stimmt denn nun?

Ausschließlich maßgeblich ist die Definition in deinen Unterlagen.