Theoretische Informatik: Algorithmus um zu testen ob Sprache Teilmenge einer anderen Sprache ist
-
Jester schrieb:
Oh ja, sofern Du Dich an dieses Zitat hältst und auch die einfach Sache, nämlich Deine Anwort, geduldig mit dem gebotenen Aufwand formulierst, sodass man sie auch lesen kann, freue ich mich regelrecht drauf.
(ist ja quasi ne art premiere ;))Natürlich halte ich mich an den Satz. Aber nicht wie Du willst.
Jester schrieb:
Also unter einer Gruppe verstehe ich eine... Gruppe: http://de.wikipedia.org/wiki/Gruppentheorie
Ach so. Diese Konzeptionalisierung zum Begriff Gruppe aus der Mathematik kannte ich nicht. Jetzt verstehe ich erst den Aufstand hier. Ok, in diesen Sinne.
Btw, über das neutrale Element muss ich nochmal refektieren ...Jester schrieb:
bullshit. eine kontextsensitive sprache wird genauso rein syntaktisch beschrieben (halt durch eine kontextsensitive grammatik) wie eine kontextfreie Sprache. Semantik in Sprachen ist ein ganz eigenes Konzept und ist für diese Art theoretischer Betrachtung wohl eher unwichtig.
Das halte ich wiederrum für Bullshit. Insbesondere zum Topic. Du willst eine Unterordnung in den formalen Sprachen erzwingen so wie Du es kennst.
Jester schrieb:
wo kommt jetzt der Graph her? Nach wie vor, eine Grammatik beschreibt die Syntax einer Sprache vollständig -- und das ganz ohne Semantik. Dazu braucht man keinen Graphen und nix. Natürlich kann man sich einen Bauen, aber dann solltest Du mal hinschreiben, wie der für eine Sprache denn genau aussieht.
Nehmen wir den typischen 4-Tupel der Grammatik:
http://de.wikipedia.org/wiki/Formale_Grammatik
G = (V,Σ,P,S)
Ihr geht davon auf aus, dass die Sprache die Teilmenge des Vokabular, Alphabet, Produktionregeln und Startsymbol ist, Teilsprache ist.Ich will (wie immer) den systemtechnischen Ansatz fahren:
G(Gesamt) = ( G(TeilSp), G(Rest), G(Korrel) )
G(TeilSp) = (V,Σ,P,S) // ist Tupel der Teilgrammitik, indizies schenke ich mir jetzt.
G(Rest) = (V,Σ,P,S) // ist Tupel des Komplements zur Gesamtgrammatik und der Teilgrammatik
Vielleicht sind die Startsymbole sogar nicht nötig.
G(Korrel) = (P,S) // Enthält das Startsymbol und die neue Produktionregeln um zwischen G(TeilSp) und G(Rest) die Gesamtgrammatik zu bilden.
Dann habe ich einen Graph aus 3-(4, 4, 2) - Tupeln.Der Vorteil des G(Korrel) ist das er von der Vokabular, Alphabet und Startsymbol der Teil- und Gesamtsprache unabhängig ist und noch nichtmal eindeutige Bezeichner der Terminal- und Nichtterminalsymbole benötigt, wenn Du das Spielchen so weiter treibst, weil die rel. Graphposition genügt. In den Produktionstregeln findest Du wichtige Abhängigkeitsbeziehungen zwischen den Sprachen, insb. kontextsensitiven Sprachen.
Jester schrieb:
stimmt, jedenfalls verwendest du fachbegriffe grundsätzlich falsch und drückst dich äußerst unpräzise aus. schön wenn dus gut findest, ich finds anstrengend, weil so wenig inhaltlich passiert wenn man die ganze zeit mit der dekodierung beschäftigt ist.
Deine Meinung.
-
Prof84 schrieb:
Nehmen wir den typischen 4-Tupel der Grammatik:
http://de.wikipedia.org/wiki/Formale_Grammatik
G = (V,Σ,P,S)
Ihr geht davon auf aus, dass die Sprache die Teilmenge des Vokabular, Alphabet, Produktionregeln und Startsymbol ist, Teilsprache ist.Wie gesagt, eine Sprache ist eine Menge an Wörtern, die mit Hilfe der die mit Hilfe dieser Grammatik gebildet werden können (wir beginnden mit S und wenden solange die Ersetzungsregeln aus P an, bis wir ein Wort aus ∑* erreichen).
Ich will (wie immer) den systemtechnischen Ansatz fahren:
G(Gesamt) = ( G(TeilSp), G(Rest), G(Korrel) )
G(TeilSp) = (V,Σ,P,S) // ist Tupel der Teilgrammitik, indizies schenke ich mir jetzt.
G(Rest) = (V,Σ,P,S) // ist Tupel des Komplements zur Gesamtgrammatik und der Teilgrammatik
Vielleicht sind die Startsymbole sogar nicht nötig.
G(Korrel) = (P,S) // Enthält das Startsymbol und die neue Produktionregeln um zwischen G(TeilSp) und G(Rest) die Gesamtgrammatik zu bilden.
Dann habe ich einen Graph aus 3-(4, 4, 2) - Tupeln.Kannst du diesen Teil mal etwas ausführlicher formulieren? Wie bildest du die Elemente der Teiltupel aus der ursprünglichen Grammatik? Und wie genau bildet sich daraus jetzt ein Graph?