Hallo zusammen, ich habe eine Frage. In einer Klausur in praktische Informatik hatten wir die Aufgabe im Anhang (hier ist die Lösung schon bei). Ich weiß nur nicht, wie man so eine Aufgabe systematisch angeht, also wenn man kein Ahnung hat, wie man so ein Wort erzeugt, kann man das nur durch Glück testen? Mal afangen und hoffen, ass man es irgendwie zusammen gebastelt bekommt... Also für die Aufgabe ist auch nicht viel Zeit, weil das eine von vielen ist. Wie kommt man schnellstmöglichst an die Lösung? Dann habe ich noch eine weitere Frage, wir haben die transitive Hülle definiert als Die Hülle mit der Eigenschaft E der Transitionsrelation ist die kleinste Relation der Tranisionsrelation, welche die Eigenschaft E erfüllt. Das sagt mir jedoch garnichts aus, deswegen habe ich auf http://de.wikipedia.org/wiki/Transitive_H%C3%BClle nachgeschlagen, das Beispiel mit den Vorgesetzten verstehe ich dort. Nur, wie bestimmt man die transitive Hülle einer Grammatik ? Dankeschön ;)
Angehängte Dateien:
-
gram.JPG
33 KB
Man muß die transitive Hülle inkognito demodulieren und mit einem Amplitudensieb die vagabundierenden Reflexpartikel konjugieren oder so...
Zu 1: Erstens gibt es nicht immer "die" Ableitung, es kann auch mehrere geben. Dann reicht es aber wahrscheinlich, irgendeine anzugeben. Für Kontextfreie Grammatiken gibt es den CYK-Algo (-> Wikipedia), allerdings ist die Grammatik aus dem Anhang nicht Kontextfrei (und erst recht nicht in Chomsky-Normalform, die für den Algo benötigt wird). Ansonsten bietet es sich an, erst einmal auszuprobieren, welche Ableitungen überhaupt vom Startsymbol aus möglich sind: (S -> LAaR -> LaaAR) +-> LaaBR -> LaBaR -> LBaaR -> LAaaR -> LaaAaR -> LaaaaAR . +-> LaaaaBR -> ... . +-> LaaaaF -> ... +-> LaaF -> LaFa -> LFaa -> aa Beachte dass dass andere Ableitungen nicht möglich waren. Mit den Fortsetzungen "..." in der Mitte kannst du zwar Weitermachen, aber da siehst du schon dass es weiter nach dem selben Prinzip abläuft, nur mit mehr "a" in der Mitte. Also kannst du dir denken (und notfalls sogar beweisen) welche Wörter in der Sprache sind und wie man sie ableitet). Wenn dieser Trick nicht funzt (z.B. zu viele Möglichkeiten), dann hilft es manchmal auch zu schauen, dass zur Ableitung eines Terminalstrings am Ende alle Nichtterminale verschwunden sein müssen. Du musst also nicht immer vom Startsymbol ausgehen, sondern kannst auch mal schauen "wenn ich den String xyz ableiten will, was könnte die letzte Produktion sein, die ich anwende". Zu 2: Die Transitive Hülle ist eigentlich für 2er-Relationen auf einer Menge M, also für Teilmengen der Menge M x M definiert. Für Grammatiken muss der Begriff erst erweitert werden, also wäre es vielleicht ganz gut mal den Kontext zu posten, in dem du das gelesen hast. Für 2er-Relationen erklär ich es an einem Beispiel: Die Vorgänger-Relation auf den Natürlichen Zahlen gilt zwischen zwei Zahlen x und y, wenn x+1=y, also "x ist Vorgänger von y" genau dann wenn "x+1=y" 4 ist Vorgänger von 5 0 ist Vorgänger von 1 1 ist Vorgänger von 2 1 ist nicht Vorgänger von 1 1 ist nicht Vorgänger von 0 1 ist nicht Vorgänger von 3 1 ist nicht Vorgänger von 5 Das letzte Beispiel ist wichtig: 1 ist zwar kleiner als 5, aber es ist nicht der direkte Vorgänger. Es ist aber der Vorgänger des Vorgängers des ... Genau darum gehts in der transitiven Hülle. Die Transitive Hülle der Vorgänger-Relation gilt zwischen x und y genau dann, wenn es eine Kette x, a1, ..., aN, y gibt, so dass zwischen je zwei Gliedern der Kette die ursprüngliche Relation gilt. Also gilt die TH von "Vorgänger" für 1 und 5, wobei die Kette "1, 2, 3, 4, 5" ist. Die Kette darf aus nichts als x und y bestehen, soll heißen in der TH gelten alle ursprünglichen Beziehungen immer noch. Die TH gilt zwischen einem Element und sich selbst nur dann, wenn die ursprüngliche Relation das tat oder es eine Kette x, a1, ..., aN, x gibt. Die TH von "Vorgänger" ist also die kleiner-Relation.
> Dann habe ich noch eine weitere Frage, wir haben die transitive > Hülle definiert als > Die Hülle mit der Eigenschaft E der Transitionsrelation ist die > kleinste Relation der Tranisionsrelation, welche die Eigenschaft E > erfüllt. Hmm, ich verstehe den Text auch nicht: Was ist die Eigenschaft E? Was ist die Relation einer Relation? Bist du sicher, dass diese Definition so richtig formuliert ist, und dass da auch nichts fehlt? Unter der transitiven Hülle der Transitionsrelation einer Grammatik kann ich mir allerdings etwas vorstellen. Die Transitionsrelation ist hier definiert (letzter Abschnitt "Formale Sprachen") http://de.wikipedia.org/wiki/Transitionsrelation die transitive Hülle hier http://de.wikipedia.org/wiki/Transitive_H%C3%BClle (hast du ja schon gefunden). Beides zusammen ergibt die transitive Hülle der Transitionsrelation. Sie enthält, salopp ausgedrückt, alle Paare von Wörtern (bestehend aus Terminal- und Nichtterminalzeichen), die durch n-fache (n in {0, 1, 2, ...}) Anwendung von Produktionen der Grammatik ineinander übergeführt werden können. Alle Wörter, die zu einem der Startsymbole in dieser Relation stehen, bilden zusammen die durch die Grammatik definierte Sprache. Frage am Rande: So etwas lernt man in der praktischen Informatik? :D
Wenn sich das praktische Informatik nennt will ich lieber nicht wissen wie die theoretische Informatik aussieht.
Hier erkennt man, daß es nur ein kleiner Schritt zwischen Genie und Wahnsinn ist.
Hallo, vielen Dank für Eure Antworten! ja ich weiß auch nicht was das mit praktischer Informatik zu tun hat auch nicht unser leztes Thema was noch viel theoretischer ist (Hoare Kalkül). Wie auch immer, muss da irgendwie durch, also bei der Definition der Hülle habe ich mich verschrieben, im Skript steht es so: Die Transitionsrelation mit der Eigenschaft E ist die kleinste Relation der die die Tranistionsrelation beinhaltet und die Eigenschaft E erfüllt. Leider verstehe ich das immer noch nicht. Hättet ihr da ein einfaches Beispiel zu und könntet die Hülle angeben, ich hoffe, dann sehe ich es. Danke soweit ;)
sorry: Die Hülle mit der Eigenschaft E der Tranistionsrelation ist die kleinste Relation, die die Tranisionsrelation beinhaltet und die Eigenschaft E erfülle :-)
meien Eigene Überlegung aufgrund Eurer Beschreibung: A -> As | dB B -> a | c | A Start: a As oder B oder da oder dc oder dAs oder dB oder dA also mehr oder weniger V vereinigt Z* also die nicht Terminalsymbole vereinigt mit allen möglichen Wörtern ??
>salopp ausgedrückt, alle >Paare von Wörtern (bestehend aus Terminal- und Nichtterminalzeichen), >die durch n-fache (n in {0, 1, 2, ...}) Anwendung von Produktionen der >Grammatik ineinander übergeführt werden können. A -> As | dB B -> a | c | A Start:A As kann durch einfaches anwenden in "dBs" überführt werden. As kann durch zweifaches anwenden in "das" überführt werden. Ist dann die transitive Hülle z.B. Hülle= {AS/dBs, AS/das} ....... n=1......n=2.... es können noch weitere Sachen durch einwaches anwenden ineinander übergehen. Wo schreibt man das dann hin ?
jochen wrote: > es können noch weitere Sachen durch einwaches anwenden ineinander > übergehen. Wo schreibt man das dann hin ? An die Klotür (von innen) oder Gummizelle
> Die Hülle mit der Eigenschaft E der Tranistionsrelation ist die > kleinste Relation, die die Tranisionsrelation beinhaltet und die > Eigenschaft E erfülle :-) Ah, jetzt kommt so langsam Licht ins Dunkel. Die Definition einer (allgemeinen) Hülle steht hier http://de.wikipedia.org/wiki/H%C3%BCllenoperator das englische Wikipedia ist hier aber etwas genauer: http://en.wikipedia.org/wiki/Closure_%28mathematics%29 In der Definition in eurem Vorlesungsskript geht es nun nicht um eine beliebige Menge sondern speziell um die Transitionsrelation. Die "bestimmten Anforderungen" aus dem deutschen Wikipedia-Artikel werden hier "Eigenschaft E" genannt, es ist aber das Gleiche damit gemeint. E kann eine beliebige Eigenschaft einer Relation sein, so z.B. die Transitivitätseigenschaft. Wählt man diese als Eigenschaft E, so nennt man die sich ergebende Hülle sinnigerweise "transitive Hülle". Nehmen wir als Beispiel die Grammatik G aus der obigen Aufgabe: W sei die (unendliche) Menge aller Wörter, die sich aus 0 oder mehr Terminal- und Nichtterminalzeichen bilden lassen: W = { epsilon, A, B, F, L, R, S, a, AA, AB, AF, AL, AR, AS, Aa, BA, BB, BF, BL, BR, BS, Ba, ... aA, aB, aF, aL, aR, aS, aa, AAA, AAB, AAF, AAL, AAR, AAS, AAa, ... AAAA, AAAB, AAAF, AAAL, AAAR, AAAS, AAAa, ... } Weiterhin sei W+ die Menge aller Wörter, die mindestens die Länge 1 haben: W+ = W \ { epsilon } Die Translationsrelation =>G (im Folgenden einfach => genannt) ist die Menge aller Paare von Wörtern aus W+ bzw. W, für die das zweite Wort aus dem ersten durch eine Produktionsregel der Grammatik ableitbar ist. Beispiele: Mit der 7. Produktionsregel lässt sich aus ABaFLL ABFaLL ableiten. Damit ist das Paar (ABaFLL, ABFaLL) ein Element von =>, d.h. für die beiden Wörter ist die Transitionsrelation erfüllt und man schreibt ABaFLL => ABFaLL Weitere Elemente von => sind: (aBRBAR, BaRBAR), Regel 5 (ALF, A), Regel 8 (AaL, aaAL) Regel 2 (LF, epsilon) Regel 8 usw. Die Transitionsrelation enthält i.Allg. unendlich viele Elemente, so auch hier. Nun kommt die transitive Hülle, ich nenne sie ==>: Diese ist nach Definition die kleinste Obermenge von => mit der Eigenschaft, dass sie transitiv ist. D.h. sie enthält mindestens die Elemente von =>, somit gilt: Wenn (w1, w2) in =>, dann (w1, w2) in ==> oder mit Relationsoperatoren geschrieben: Wenn w1 => w2, dann w1 ==> w2 Damit die neue Relation transitiv wird, muss sie aber noch mehr Elemente enthalten. Die Transitivität einer Relation R im Allgemeinen ist so definiert: Wenn x R y und y R z, dann gilt auch x R z (für beliebige x, y, z) Auf die transitive Hülle der Transitionsrelation bezogen bedeutet dies: Wenn w1 ==> w2 und w2 ==> w3 dann muss auch w1 ==> w3 gelten bzw. Wenn (w1, w2) in ==> und (w2, w3) in ==>, dann auch (w1, w3) in ==> Man kann also die transitive Hülle ==> dadurch bilden, dass man sie erst einmal mit den Elementen (Paaren) von => füllt. Dann sucht man alle Ketten von Paaren, die sich wie Dominosteine aneinanderfügen lassen. Das erste Wort des ersten Paares und das zweite Wort des letzten Paares werden als neues Paar in ==> eingetragen. Hat man das für alle Paare gemacht, ist ==> die neue Relation mit den gewünschten Eigenschaften. Die Relation ==> enthält nun alle Wortpaare, für die das zweite Wort durch ein- oder mehrfache (also 1-, 2-, 3-, ... fache) Anwendung von Produktionsregeln der Grammatik G aus dem ersten abgeleitet werden kann. Oft soll der Vollständigkeit halber die neue Relation zusätzlich auch diejenigen Wortpaare enthalten, die durch die 0-fache Anwendung der Produktionsregeln ineinander abgeleitet werden können. Eine Ableitung mit 0 Produktionsregeln führt logischerweise wieder auf das gleiche Wort, also fügt man der neuen Relation alle Paare mit zwei gleichen Wörtern hinzu. Die Relation hat nun die Eigenschaft, dass für alle Wörter w gilt (w, w) in ==> bzw. w ==> w Diese Eigenschaft einer Relation nennt sich Reflexivität. Die Eigenschaft E ist nun die Kombination aus Transitivität und Reflexivität, folglich heißt die neue Relation "reflexiv-transitive Hülle". Alles klar? @Dirk J. und Izmir Übel: Was meint ihr dazu? Bin schon auf eure nächsten humorvollen Kommentare gespannt :)
Ich geb's auf, das ist mir alles zu abgehoben. Ich geh jetzt schlafen (ist hier jetzt 0.30 Uhr), ich lebe nämlich auf dem 124. Längengrad Ost. Gute Nacht.
Wenn das praktische Informatik ist, möcht ich nicht wissen, was theoretische ist....*schauder*
Christian R. wrote: > Wenn das praktische Informatik ist, möcht ich nicht wissen, was > theoretische ist....*schauder* Hmmmm, sieht mir auch eher aus wie unpraktische Informatik. ;-)))
Gaststar schrieb: > Wenn sich das praktische Informatik nennt will ich lieber nicht > wissen wie die theoretische Informatik aussieht. Christian R. schrieb: > Wenn das praktische Informatik ist, möcht ich nicht wissen, was > theoretische ist....*schauder* Endlich mal ein Thread, wo sich alle 100%ig einig sind :D @jochen: Welche Hochschule bietet denn diesen praxisnahen Studiengang an? Und gibt es tatsächlich auch noch eine Klausur in theoretischer Informatik? Kannst du da auch mal eine Aufgabe posten?
Ja würde ich auch gerne wissen. Zufällig in Oldenburg (Prof. Theel) ? Das kommt mir sehr bekannt vor.
@yalu, irgendwie hab ich deinen Beitrag überlesen, sehns mir morgen an, schonmal vielen Dank! Nee das ganze kommt aus der Vorlesung in Ulm ;D bis dann !
Hier bin ich wieder! @ Jochen An deiner Stelle würde ich vom Prof eine eidesstattliche Versicherung verlangen, dass man mit der Lösung dieser Probleme das dicke Geld verdienen kann. Ich glaube, du hast es mit Sadisten zu tun.
Izmir Übel wrote: > An deiner Stelle würde ich vom Prof eine eidesstattliche Versicherung > verlangen, dass man mit der Lösung dieser Probleme das dicke Geld > verdienen kann. Das richtig dicke Geld ist es nicht und aufgrund ungünstiger Geschlechterverteilung fallen auch andere Vorteile eher weg - aber man kann damit immerhin nachweislich Professor werden. ;-) > Ich glaube, du hast es mit Sadisten zu tun. Seltsam ist eigentlich nur die Einstufung als praktische Informatik. Als theoretische Informatik wär's normal. Immerhin ist Informatik eng mit der Mathematik verwandt.
Ein Professor für Informatik, Mann, ist das ein Traumberuf. Damit kann man Frauen aufreissen, ist der Mittelpunkt auf jeder Party. Vollbusige Blondinen schmeißen sich an einen ran und wollen nur eines: ein ausführliches Einzelgespräch über die Mengenlehre, aber mit transparenter Hülle, denn sie wollen ja nicht auch gehirnschwanger werden...
Ich habe noch eine Frage zu dem Beitrag von yalu ( vielen Dank übrigens
;) )
Die Grammatik war G = ({A,B, F,L,R, S}, {a}, P, S)
meinst du dann mit der Menge W alle Wörter, die in beliebiger Anreihung
von
A,B, F,L,R, S und a entstehen also auch z.b.
RRSFaaaaaABF?
Dann habe ich noch eine Frage zur Bestimmtung der transitiven Hülle:
In der Menge => sind ja hier doch die Paare
(BAaFaB, BaaAFaB) und
********
(BaaAFaB, BaaAFBa)
********
verstehe ich dann richtig, dass
(BAaFaB,BaaAFBa) in der transitiven Hülle liegt?
> meinst du dann mit der Menge W alle Wörter, die in beliebiger > Anreihung von A,B, F,L,R, S und a entstehen also auch z.b. > RRSFaaaaaABF? Ja. > verstehe ich dann richtig, dass (BAaFaB,BaaAFBa) in der transitiven > Hülle liegt? Ja, und ebenso (BAFaaB, BaaAFBa), weil BAaaFB => BAaFaB => BaaAFaB => BaaAFBa Noch kurz ein paar Worte zu Theorie und Praxis: Meine Frage von oben, was das mit der praktischen Informatik zu tun hat, bezog sich weniger auf die transitive Hülle, sondern auf die nicht kontextfreien Gramma- tiken, zu denen G ja gehört. Für letztere fällt mir keine praktische Anwendung ein (lasse mich aber gerne eines besseren belehren), da alle nichtexperimentellen Programmiersprachen kontextfrei sind. Transitive Hüllen über Grammatiken oder Teilen davon spielen hingegen bei der Entwicklung von Generatoren für tabellengesteuerte Parser (wie bspw. yacc und bison) eine Rolle und haben daher durchaus praktischen Nutzen. Das fällt dann unter das Thema Compilerbau, der normalerweise nicht zur theoretischen Informatik gezählt wird.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.