mikrocontroller.net

Forum: Offtopic praktische Informatik (transitive Hülle)


Autor: jochen (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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 ;)

Autor: Dirk J. (dirk-cebu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man muß die transitive Hülle inkognito demodulieren und mit einem 
Amplitudensieb die vagabundierenden Reflexpartikel konjugieren oder 
so...

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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

Autor: Gaststar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn sich das praktische Informatik nennt will ich lieber nicht wissen 
wie die theoretische Informatik aussieht.

Autor: Dirk J. (dirk-cebu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier erkennt man, daß es nur ein kleiner Schritt zwischen Genie und 
Wahnsinn ist.

Autor: Izmir Übel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe mein ganzes bisheriges Leben vergeudet!

Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;)

Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sorry:
Die Hülle mit der Eigenschaft E der Tranistionsrelation ist die kleinste 
Relation, die die Tranisionsrelation beinhaltet und die Eigenschaft E 
erfülle :-)

Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

??

Autor: Izmir Übel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das hätte ich jetzt aber wirklich nicht vermutet!

Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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 ?

Autor: Dirk J. (dirk-cebu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kennt noch jemand "dbddhkp"?

Autor: Dirk J. (dirk-cebu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
machts Spaß, Dirk?

hat jemand eine Idee?

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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 :)

Autor: Dirk J. (dirk-cebu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Christian R. (supachris)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn das praktische Informatik ist, möcht ich nicht wissen, was 
theoretische ist....*schauder*

Autor: Dieter Werner (dds5)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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. ;-)))

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Mighty (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja würde ich auch gerne wissen. Zufällig in Oldenburg (Prof. Theel) ?
Das kommt mir sehr bekannt vor.

Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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 !

Autor: Izmir Übel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Dirk J. (dirk-cebu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: jo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.