Hi,
ist die folgende Regel Chomsky-1 konform ?
BC -> CB
Laut der Definition müsste eine Variable links von der Regel, die in einem Kontext steht, ersetzt werden durch irgendetwas anderes ausser „epsilon“, wobei der Kontext noch erhalten bleibt. Wenn ich B als die zu ersetzende Variable hernehme, dann ist C der Kontext. Auf der rechten Seite der Regel bleibt aber der Kontext nicht erhalten.
Viele Grüße,
Tris
Hallo,
das hängt davon ab, wie ihr kontextsensitiv (Chomsky-1) definiert habt. Man kann gleichwertig fordern, daß für jede Produktionsregel u -> v (wobei u,v Wörter aus Terminalen und Nichtterminalen sein können) |u| CB ließe sich z.B. umschreiben zu BC -> HC, HC -> HB, HB -> CB, wobei H ein neues Symbol ist.
Gruss
Enno
Hallo,
Du scheinst Dich sehr gut auszukennen.
Heisst das im Endeffekt, dass zwei Arten von Grammatiken existieren, die alle Chomsky-1 Sprachen aufbauen ?
Bei der ursprünglichen Definition ersetzt man eine Variable durch etwas beliebiges (ausser „epsilon“), wobei der Kontext erhalten bleibt. Dann kann man zeigen, dass monotone Grammatiken gleichmächtig sind. D.h. es gilt |u| SbT eine gültige Regel für eine Chomsky-1 Grammatik, oder ?
Danke und Grüße,
Tris
Hallo,
ja monotone und kontextsensitive Grammatiken beschreiben dieselbe Sprachklasse. Insbesondere findet sich zu jeder monotonen immer eine kontextsensitive Grammatik.
Ist das korrekt ?
Ja.
Es wäre dann z.B. aST -> SbT eine gültige Regel für eine
Chomsky-1 Grammatik, oder ?
Ja aber so wie bei Euch kontextsensitiv definiert wurde, ist diese Grammatik bzw. diese Regel zunächst nur monoton. Man müßte sie und ggf. andere erst durch kontextsensitive Regeln ersetzen, um die Kontextsensitivität z.Z., falls der Bezug monoton kontextsensitiv noch nicht Bestandteil der Vorlesung war.
Gruss
Enno