Theoretische Informatik: Algorithmus um zu testen ob Sprache Teilmenge einer anderen Sprache ist
-
Jester schrieb:
Prof84 schrieb:
Jaaa! - Also wenn Du eine Grammtik mit z.B. EBNF als Gruppen(Mengen) darstellen kannst
Halt stop, Du meinst Mengen und nicht Gruppen oder? Gruppen haben damit nix zu tun... oder doch?
Soll das jetzt ein Diskurs sein Kategorientheorien != Mengetheorie. Aus der Argumentation mag Mengen richtig sein. Aber ich finde Gruppen auch nicht so verkehrt. Mit dem was ich mit Sprachen mache sowieso nicht.
Jester schrieb:
was genau meinst Du mit Literalen
Das: http://de.wikipedia.org/wiki/Literal
Jester schrieb:
und was heißt "zuordnen kannst"?
Das: http://de.wikipedia.org/wiki/Relationen
Jester schrieb:
Dass sie zur Sprache gehören?
Ja.
Jester schrieb:
Meinst Du Wörter die zur Sprache gehören?
Was für eine Gesamtgrammatik von was? Ist L(B) eine Grammatik oder eine Sprache?Definieren wir erst mal den Unterschied bei formalen Sprachen zwischen Sprache und Grammatik:
Eine Sprache besteht aus der Semantik, Grammatik und Syntax.(Und eigentlich Morphologie, gibt es bei den Formalen Sprachen meistens nicht).
Sematik enthält die Symboltabelle (Alphabet, Begriffe, Wörter) und Relationen mit bezeicheneden Sterotypen -> Semantische Netze, Ausdrücke.
Grammatik beinhaltet die Token, Literale, Termale, Determinale und Relationen (Gruppen bzw. Mengen - Ich finde Gruppen immer noch richtig.)
Syntax (Zusammenhang) ist das Gesamtgerüst aus Grammatik und Semantik für die Satzbildung.
Bei kontextfreien Sprachen geht die Semantik vollständig in die Grammatik über -> (E)BNF.
Bei kontextsensitiven Sprachen enthält die Semantik funktionale Zusammenhänge die nicht vollständig in die Grammatik überführt werden können. Dennoch kann eine Kontextfreie Grammatik eine Teilmenge der Kontextsensitive Grammatik sein.Jester schrieb:
Welche Relationen, wo kommen da jetzt irgendwelche Graphen her?
Fehlt noch die Syntax, die weil Grammatik und Semantik zusammenfallen bei Kontextfreien Sprachen glech der Grammatik wäre. Bei kontextsensitiven eben nicht. Da tauchen Stereotypen zwischen Semantik, Grammatik und Syntax auf. Und èvola, es tauchen Graphen auf in der Sprache. Eine Kontextsensitive Sprache ist Teilsprache wenn sie Subgragh der Sprache ist.
Jester schrieb:
Wenn letzteres, dann ist wahrscheinlich höchstens L(A) Teilmenge von L(B), aber nicht L(A) Element von L(B).
Und jetzt erkläre Du mir bitte nochmal den Unterschied wenn wir über zwei Sprschen reden.
Jester schrieb:
Tut mir leid, das sind ne menge Fragen, aber ich habe da wirklich ein ganz grundsätzliches Problem, dass ich mit der Art wie Du Fachbegriffe verwendest nicht umgehen kann.
Ich habe ohne Zweifel ein Out-of-the-box-Denken und finde es gut.
-
Jester schrieb:
Tut mir leid, das sind ne menge Fragen, aber ich habe da wirklich ein ganz grundsätzliches Problem, dass ich mit der Art wie Du Fachbegriffe verwendest nicht umgehen kann.
Ich glaub das ist das erklärte Ziel von Prof84.
-
Prof84 schrieb:
Mit was mit Sprachen mache sowieso nicht.
Ich finds immer schade, wenn man sich bei wahrscheinlich einfachen Sätzen überlegen muss, was sie denn bedeuten mögen. Ich hab keine Ahnung.
Definieren wir erst mal den Unterschied bei formalen Sprachen zwischen Sprache und Grammatik:
Eine Sprache besteht aus der Semantik, Grammatik und Syntax.(Und eigentlich Morphologie, gibt es bei den Formalen Sprachen meistens nicht).
Die meisten Sprachen werden auch nicht von einer Grammatik erzeugt, jedenfalls nicht in der Form, in der ich es kenne.
Grammatik beinhaltet die Token, Literale, Termale, Determinale und Relationen (Gruppen bzw. Mengen - Ich finde Gruppen immer noch richtig.)
Wo siehst du da ne Gruppenstruktur? Was ist das Inverse eines Literals?
Und èvola es tauchen Graphen auf in der Sprache.
Ich sehe sie nicht. Aber gut, ich hab auch vom ganzen Abschnitt ziemlich wenig verstanden.
Jester schrieb:
Wenn letzteres, dann ist wahrscheinlich höchstens L(A) Teilmenge von L(B), aber nicht L(A) Element von L(B).
Und jetzt erkläre Du mir bitte nochmal den Unterschied wenn wir über zwei Sprschen reden.
Sprachen sind doch nur Teilmengen von ∑*. Warum fällt der Unterschied zwischen Element und Teilmenge weg=
-
Prof84 schrieb:
Definieren wir erst mal den Unterschied bei formalen Sprachen zwischen Sprache und Grammatik:
Eine Sprache besteht aus der Semantik, Grammatik und Syntax.(Und eigentlich Morphologie, gibt es bei den Formalen Sprachen meistens nicht).
Sematik enthält die Symboltabelle (Alphabet, Begriffe, Wörter) und Relationen mit bezeicheneden Sterotypen -> Semantische Netze, Ausdrücke.
Grammatik beinhaltet die Token, Literale, Termale, Determinale und Relationen (Gruppen bzw. Mengen - Ich finde Gruppen immer noch richtig.)
Syntax (Zusammenhang) ist das Gesamtgerüst aus Grammatik und Semantik für die Satzbildung.
Bei kontextfreien Sprachen geht die Semantik vollständig in die Grammatik über -> (E)BNF.
Bei kontextsensitiven Sprachen enthält die Semantik funktionale Zusammenhänge die nicht vollständig in die Grammatik überführt werden können. Dennoch kann eine Kontextfreie Grammatik eine Teilmenge der Kontextsensitive Grammatik sein.Nochmal langsam zum Mitschreiben: Eine Sprache in der theoretischen Informatik ist eine Menge von Wörtern, nicht mehr und nicht weniger. Grammatiken und Automaten sind eine Möglichkeit, diese Sprachen zu beschreiben. Es gibt übrigens auch kontextsensitive Grammatiken (die die Syntax einer kontextsensitiven Sprache beschreiben - und sogar noch allgemeinere Grammatiken. Und es gibt sogar Sprachen, die nicht durch eine Grammatik dargestellt werden können.
Ich habe ohne Zweifel ein Out-of-the-box-Denken und finde es gut.
Dann erwarte aber nicht, daß irgendjemand mit deinem Denken umgehen kann, wenn du die Grundgebriffe völlig neu definierst.
-
Prof84 schrieb:
Jester schrieb:
Prof84 schrieb:
Jaaa! - Also wenn Du eine Grammtik mit z.B. EBNF als Gruppen(Mengen) darstellen kannst
Halt stop, Du meinst Mengen und nicht Gruppen oder? Gruppen haben damit nix zu tun... oder doch?
Soll das jetzt ein Diskurs sein Kategorientheorien != Mengetheorie. Aus der Argumentation mag Mengen richtig sein. Aber ich finde Gruppen auch nicht so verkehrt. Mit dem was ich mit Sprachen mache sowieso nicht.
Also unter einer Gruppe verstehe ich eine... Gruppe: http://de.wikipedia.org/wiki/Gruppentheorie
Jester schrieb:
was genau meinst Du mit Literalen
Das: http://de.wikipedia.org/wiki/Literal
Jester schrieb:
und was heißt "zuordnen kannst"?
Das: http://de.wikipedia.org/wiki/Relationen
Jester schrieb:
Dass sie zur Sprache gehören?
Ja.
Ich weiß sowohl was ein Literal ist und was eine Relation ist, leider kannst Du anscheinend nicht so gut ausdrücken was du sagen möchtest... dass Du "ein literal einer Sprache zuordnen kannst" soll also nix anderes heißen als "wenn ein Wort zur Sprache gehört"? Danke, das hätte ich gleich verstanden.
Jester schrieb:
Meinst Du Wörter die zur Sprache gehören?
Was für eine Gesamtgrammatik von was? Ist L(B) eine Grammatik oder eine Sprache?Definieren wir erst mal den Unterschied bei formalen Sprachen zwischen Sprache und Grammatik:
Eine Sprache besteht aus der Semantik, Grammatik und Syntax.(Und eigentlich Morphologie, gibt es bei den Formalen Sprachen meistens nicht).
Sematik enthält die Symboltabelle (Alphabet, Begriffe, Wörter) und Relationen mit bezeicheneden Sterotypen -> Semantische Netze, Ausdrücke.
Grammatik beinhaltet die Token, Literale, Termale, Determinale und Relationen (Gruppen bzw. Mengen - Ich finde Gruppen immer noch richtig.)
Syntax (Zusammenhang) ist das Gesamtgerüst aus Grammatik und Semantik für die Satzbildung.
Bei kontextfreien Sprachen geht die Semantik vollständig in die Grammatik über -> (E)BNF.
Bei kontextsensitiven Sprachen enthält die Semantik funktionale Zusammenhänge die nicht vollständig in die Grammatik überführt werden können. Dennoch kann eine Kontextfreie Grammatik eine Teilmenge der Kontextsensitive Grammatik sein.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.
Jester schrieb:
Welche Relationen, wo kommen da jetzt irgendwelche Graphen her?
Fehlt noch die Syntax, die weil Grammatik und Semantik zusammenfallen bei Kontextfreien Sprachen glech der Grammatik wäre. Bei kontextsensitiven eben nicht. Da tauchen Stereotypen zwischen Semantik, Grammatik und Syntax auf. Und èvola, es tauchen Graphen auf in der Sprache. Eine Kontextsensitive Sprache ist Teilsprache wenn sie Subgragh der Sprache ist.
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.
Jester schrieb:
Wenn letzteres, dann ist wahrscheinlich höchstens L(A) Teilmenge von L(B), aber nicht L(A) Element von L(B).
Und jetzt erkläre Du mir bitte nochmal den Unterschied wenn wir über zwei Sprschen reden.
doh, wir müssen aber nicht diskutieren, dass "A Teilmenge B" und "A Element von B" zwei unterschiedliche Dinge sind, oder?
Jester schrieb:
Tut mir leid, das sind ne menge Fragen, aber ich habe da wirklich ein ganz grundsätzliches Problem, dass ich mit der Art wie Du Fachbegriffe verwendest nicht umgehen kann.
Ich habe ohne Zweifel ein Out-of-the-box-Denken und finde es gut.
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.
-
Michael E. schrieb:
Grammatik beinhaltet die Token, Literale, Termale, Determinale und Relationen (Gruppen bzw. Mengen - Ich finde Gruppen immer noch richtig.)
Wo siehst du da ne Gruppenstruktur? Was ist das Inverse eines Literals?
Bezeichner!Sprachen sind doch nur Teilmengen von ∑*. Warum fällt der Unterschied zwischen Element und Teilmenge weg=
Nicht in meinen Universum.
Eine Sprache in der theoretischen Informatik ist eine Menge von Wörtern, nicht mehr und nicht weniger.
Nicht in meinem Universum. Mag sein, dass die Theos jedes Signal als Sprache interpretieren. Ich mache das nicht.
Es gibt übrigens auch kontextsensitive Grammatiken (die die Syntax einer kontextsensitiven Sprache beschreiben - und sogar noch allgemeinere Grammatiken.
Nicht in meinem Universum. Per Definition ist die Semantik die unterste Ebene zur Metaphysik. Sobald Du die Grammatik mit der Semantik verbindest hast Du eine Semantik und nicht eine Grammatik. Beispiel aus der natürlichen Sprache:
Der Akkussativ eines bestimmten Nomens hätte eine ganz andere Bedeutung. Dann ist der Akkusativ nicht mehr der Grammatik sondern der Semantik zuzuordnen.Und es gibt sogar Sprachen, die nicht durch eine Grammatik dargestellt werden können.
Wunderbar! Und wo würdest Du in der Chomsky Hierarchie einordnen?! Daran hatte ich jetzt nicht Gedacht im Eifer des Gefechts.
Dann erwarte aber nicht, daß irgendjemand mit deinem Denken umgehen kann, wenn du die Grundgebriffe völlig neu definierst.
Ach, ihr seit noch harmlos. Alle drei Monate haben wir ein Neuzugang sitzen der anfangs immer die Krise bekommt, wenn ich gängige Fachmodelle in der Luft zerreiße. Aber dann schnallt er das plötzlich seine Anomalien verschwinden, die er in Dekaden nicht wegbekommen hat. Nach ein paar Sitzungen ist er dann abgeschliffen.
Die Menschen, die die Geduld haben, auch einfache Sachen vollkommen zu machen, gewinnen die Fähigkeit, auch schwere Sachen einfach zu meistern. (der olle Schiller)
@Jester:
Morgen oder später.
-
Prof84 schrieb:
Nicht in meinen Universum.
Es muß ziemlich einsam in deinem Universum sein
Aber wenn du mit anderen Menschen reden willst, benötigen wir eine einheitliche Benennungsgrundlage.Per Definition ist die Semantik die unterste Ebene zur Metaphysik. Sobald Du die Grammatik mit der Semantik verbindest hast Du eine Semantik und nicht eine Grammatik. Beispiel aus der natürlichen Sprache:
Der Akkussativ eines bestimmten Nomens hätte eine ganz andere Bedeutung. Dann ist der Akkusativ nicht mehr der Grammatik sondern der Semantik zuzuordnen.Die Semantik steht hier gar nicht zur Debatte. Die wird erst interessant, wenn wir versuche, den durch die Grammatik gebildeten Wörtern eine Art von Bedeutung zu geben (z.B. der Zweck des Akkusativ oder die Effekte, die ein C++ Programm bewirkt).
Und es gibt sogar Sprachen, die nicht durch eine Grammatik dargestellt werden können.
Wunderbar! Und wo würdest Du in der Chomsky Hierarchie einordnen?! Daran hatte ich jetzt nicht Gedacht im Eifer des Gefechts.
nirgends - die Chomsky-Hierarchie wird über die Mächtigkeit der erlaubten Grammatiken gebildet, also können "nicht-grammatische" Sprachen auch nicht dort eingeordnet werden. (eventuell könnte man eine Klasse Chomsky -1 dafür definieren :D)
-
Prof84 schrieb:
Die Menschen, die die Geduld haben, auch einfache Sachen vollkommen zu machen, gewinnen die Fähigkeit, auch schwere Sachen einfach zu meistern. (der olle Schiller)
@Jester:
Morgen oder später.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 ;))
-
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?