Diskussion:Kontextsensitive Grammatik

Herkunft aus Chomsky-Hierarchie

Dieser Artikel sollte (und so ist es geplannt) mit selbigen Thema gefüllt werden, also aus Chomsky-Hierarchie herausgearbeitet werden ;) --Kleinvieh macht auch Mist 18:06, 29. Nov 2005 (CET)

Und warum passiert hier seit 2005 nix? :) (nicht signierter Beitrag von 85.179.244.239 (Diskussion | Beiträge) 11:28, 22. Jul 2009 (CEST))

Beispiele

Hier ist nichts mit Quellen belegt. Ein Beweis fuer das Beispiel sollte hier gebracht oder in einer entsprechenden Quelle vorhanden sein. --87.176.245.48 23:28, 27. Dez. 2009 (CET)

Das Beispiel ist sowieso fehl am Platz. Kontextsensitive Sprachen haben ihren eigenen Artikel. Hier gehört hauptsächlich ein Beispiel für die Grammatik hin. Habe daher das andere Beispiel entfernt. --Zahnradzacken 01:42, 28. Dez. 2009 (CET)

Das Beispiel ist besonders schlecht weil die Regeln $AB\rightarrow BA,CA\rightarrow AC$ usw. gar nicht erlaubt sind. Das steht etwa 5 Zeilen weiter oben. Wollte ich nur mal anmerken. Hätte mich da fast für die Klausur drauf verlassen... - 17.02.10 (nicht signierter Beitrag von 92.230.248.35 (Diskussion | Beiträge) 18:00, 17. Feb. 2010 (CET))

Sehr richtig, mein Fehler, falsche Stelle im Buch betrachtet. Die englische WP hats richtig zitiert.. Wird korrigiert.

Übrigens schade, dass es bisher keinen deutschen Artikel zu en:Noncontracting grammar gibt, dort hätte das Beispiel besser gepasst. --Zahnradzacken 19:13, 17. Feb. 2010 (CET)

CSG vs. Monotone Grammatik

Der Artikel enthält ja Falschinformationen. Beispielsweise "kontextsensitiv (Typ-1), wenn für jede Produktionsregel $w_{1}\rightarrow w_{2}$ gilt: $\left|w_{1}\right|\leq \left|w_{2}\right|$." stimmt ja nicht. Das heißt nur, dass die Grammatik monoton ist. Eine Grammatik ist genau dann kontextsensitiv, wenn nur ein Nonterminal ersetzt wird und der Kontext erhalten bleibt. Es stimmt zwar, dass es zu jeder monotonen eine kontextsensitive Grammatik gibt und auch umgekehrt, aber nicht automatisch, dass jede monotone Grammatik kontextsensitiv ist. Vielleicht könnte sich hier mal ein Experte ein wenig austoben. (nicht signierter Beitrag von Leon Alberti (Diskussion | Beiträge) 12:32, 24. Mär. 2010 (CET))

Siehe auch die Diskussion zur Chomsky-Hierarchie. Es gibt verschiedene Betrachtungsweisen von verschiedenen Autoren (daher auch mein "Fehler", siehe weiter oben). Richtigstellung wird geschehen. --Zahnradzacken 13:07, 24. Mär. 2010 (CET)

Fehlerhaftes Beispiel

Momentan steht folgendes im Absatz "Beispiel":

xxxxxxxxxx Die kontextsensitive Sprache $L=\{a^{n}b^{n}c^{n}\mid n\geq 1\}$ der Wörter, die aus genauso vielen a wie folgenden b und genauso vielen folgenden c besteht, wird durch folgende kontextsensitive Grammatik erzeugt:

$G=(N,T,P,S)$ mit Terminalsymbolen $T=\{a,b,c\}$ und Nicht-Terminalen $N=\{B,C,H,S\}$ sowie den Produktionsregeln $P:$

1. $S\rightarrow aSBC\mid aBC$
2. $CB\rightarrow HB$
3. $HB\rightarrow HC$
4. $HC\rightarrow BC$
5. $aB\rightarrow ab$
6. $bB\rightarrow bb$
7. $bC\rightarrow bc$
8. $cC\rightarrow cc$

Das Wort $aabbcc\in L$ lässt sich dann folgendermaßen erzeugen (der jeweils im nächsten Schritt ersetzte Kontext ist unterstrichen):

${\begin{array}{l}{\underline {S}}\Rightarrow _{1}a{\underline {S}}BC\Rightarrow _{1}aaB{\underline {CB}}C\Rightarrow _{2}aaB{\underline {HB}}C\\\Rightarrow _{3}aaB{\underline {HC}}C\Rightarrow _{4}a{\underline {aB}}BCC\Rightarrow _{5}aa{\underline {bB}}CC\\\Rightarrow _{6}aab{\underline {bC}}C\Rightarrow _{7}aabb{\underline {cC}}\Rightarrow _{8}aabbcc\end{array}}$

xxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxx

Die Grammatik hat also auch folgende Ableitung:

${\underline {S}}\Rightarrow a{\underline {S}}BC\Rightarrow _{1}aa{\underline {S}}BCBC\Rightarrow _{1}aaaB{\underline {CBCB}}C\Rightarrow _{2}aaaB{\underline {HBHB}}C\Rightarrow _{2}aaaBHC{\underline {HC}}C$ $\Rightarrow _{1}aaaBH{\underline {CB}}CC\Rightarrow _{1}aaaBH{\underline {HB}}CC\Rightarrow _{1}aaaBH{\underline {HC}}CC\Rightarrow _{1}aaaB{\underline {HB}}CCC$ $\Rightarrow _{1}aaaB{\underline {HC}}CCC\Rightarrow _{1}aaaBBCCCC\Rightarrow _{1}aaaBBCCCC\Rightarrow _{*}aaabbcccc$ und $aaabbcccc\notin L$. Daraus folgt, dass diese Grammatik nicht die beschriebene Sprache erzeugt. Ich habe das Beispiel deshalb entfernt. --MartinThoma 18:34, 6. Feb. 2012 (CET)

Ich kann deine Ableitung nicht nachvollziehen. Du schreibst fast überall $\Rightarrow _{1}$, obwohl du nur zweimal die erste Ableitungsregel verwendest. Bei deinem achten Schritt sehe ich darum nicht mehr, wieso dieser Schritt möglich sein sollte. Mit welcher Regel gelingt dir also der achte Schritt $aaaBHHBBC\Rightarrow _{1}aaaBCHHCBC$? --Zahnradzacken 22:04, 6. Feb. 2012 (CET)

Sorry, ich hatte einen Tippfehler gemacht. Ich habe es nun nochmals etwas sauberer geschrieben. Wenn man sich das Wort, sobald es die Länge 9 (Terminale + Nichtterminale) erreicht hat auf ein karriertes Blatt Papier schreibt und die Ableitungen untereinander macht, sieht man es besser. Ich hoffe ich habe mich nun nicht wieder vertippt. --MartinThoma 22:36, 6. Feb. 2012 (CET)

Danke, jetzt sehe ich es. Ich kann die Quelle von damals nicht mehr auftreiben, in der vierten Ausgabe des Buchs wird aber eine andere Definition von kontextfreien Grammatiken benutzt. Entweder es war ein Fehler im Buch oder ich habe falsch übertragen. Auf jeden Fall ist es gut, dass du es bemerkt hast. Hier wird übrigens gezeigt, wie man es richtig macht. Es gibt aber auch andere Ausgangsgrammatiken für diese Sprache, vielleicht bekommt man es auch kürzer hin? Geht man hiernach, könnte es folgende Regelmenge tun:

1. $S\rightarrow aSBC\mid aBC$
2. $CB\rightarrow CB'$
3. $CB'\rightarrow HB'$
4. $HB'\rightarrow HC$
5. $HC\rightarrow BC$
6. $aB\rightarrow ab$
7. $bB\rightarrow bb$
8. $bC\rightarrow bc$
9. $cC\rightarrow cc$

--Zahnradzacken 00:19, 7. Feb. 2012 (CET)

Ich habe morgen und übermorgen eine Klausur, hoffe aber am Wochenende Zeit zu haben. Ich glaube, dass in meinem Skript zu Theoretischen Grundlagen der Informatik mindestens zwei beispiele für kontextsensitive Sprachen mit den dazugehörigen Grammatiken sind. Diese werde ich dann als Beispiele einfügen. Die waren glaube ich auch kürzer und verständlicher. --MartinThoma 06:51, 7. Feb. 2012 (CET)

Gerade habe ich eine (hoffentlich) korrekte Grammatik zu der beschriebenen Sprache in einem Buch über Theoretische Informatik gefunden. Ich habs mal mit der Quellenangabe hinzugefügt. Damit ist dieser Abschnitt für mich erledigt. --MartinThoma 16:55, 11. Feb. 2012 (CET)

Das ist zwar eine Grammatik für die Sprache, aber Schöning definiert kontextsensitive Grammatiken anders als der Artikel hier. Die Regel $CB\rightarrow BC$ ist nach der Definition hier nicht erlaubt. Siehe dazu die früheren Diskussions-Abschnitte #Beispiele und #CSG vs. Monotone Grammatik, sowie den passenden Abschnitt im Artikel Kontextsensitive Grammatik#Kontextsensitive und monotone Grammatiken. --Zahnradzacken 17:31, 11. Feb. 2012 (CET)

Nachtrag: Die Regel $CB\rightarrow BC$ lässt sich aber durch die vier kontextsensitiven Regeln oben ersetzen. Der Fehler, auf den du aufmerksam gemacht hast, war, dass die alte Grammatik drei falsche Ersatzregeln verwendet hat. --Zahnradzacken 17:55, 11. Feb. 2012 (CET)

Definition

• S kommt auf keiner rechten Seite einer Produktionsregel vor

fällt bei der hier beschriebenen umgeformten Form weg.

Ergänzung um die Definition "P der Form $u\rightarrow v$ mit $u\in V^{+}$,$v\in ((V\setminus \{S\})\cup \Sigma )^{+}$ und $|u|\leq |v|$ oder $S\rightarrow \epsilon$" (nicht signierter Beitrag von 2001:7C0:409:8B23:725A:B6FF:FE5E:743A (Diskussion | Beiträge) 11:23, 21. Nov. 2013 (CET))

Was genau willst du ergänzen und was soll wegfallen? Sieht so aus, als wolltest du alles, was in der Definition zu "P" steht, durch deine Definition ersetzen. Dann ist es aber keine "Umformung", sondern Definition für etwas Anderes – siehe Kontextsensitive Grammatik#Kontextsensitive und monotone Grammatiken. --Zahnradzacken (Diskussion) 19:24, 23. Nov. 2013 (CET)

Einseitige Normalform

Rozenberg und Salomaa, Handbook of Formal Languages, S.190 verweist lediglich auf eine (ebenfalls englische) Publikation: M. Penttonen, One-Sided and Two-Sided Context in Formal Grammars, Information and Control, 25 (1974), 371-392. (Dank an User:Zahnradzacken für diese Auskunft). Ich fände es hilfreich, wenn auch der Artikel von Penttonen direkt in der Wikipedia referenziert wird, statt nur der Buchseite die dann doch nur auf den Artikel verweist, insbesondere da der Artikel online leichter verfügbar ist als das Handbuch. --Carsten Milkau (Diskussion) 10:49, 2. Okt. 2015 (CEST)