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 ;)
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
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.
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?
@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.
gram.JPG
(33 KB)
