[FoSAP] Kurze Fragen Thread

[aRo]

Hallo!

Vielleicht können wir ja in diesem Thread kurze Fragen stellen, von denen wir denken, dass sie nicht zu lange zur Beantwortung brauchen.

Ich mache mal den Anfang:

Kann mir jemand von euch erklären, wie das Mischprodukt (VL2, Folie15) gemeint ist? Irgendwie werde ich aus dieser Definition absolut nicht schlau. Kann man die vielleicht in Worten beschreiben?

Dankeschön!

[NightmareVirus]

du nimmst ein Wort aus der ersten Menge, und ein Wort aus der zweiten Menge. im Shuffleprodukt sind jetzt alle Wörter die man zusammenschieben kann wobei die Reihenfolge der Buchstaben aus dem ersten und die Rreihenfolge der Buchstaben aus dem zweiten jeweils gleich bleibt.
Quasi wie das Mergen beim Mergesort, da bleibt ja auch die Reihenfolge der beiden Teilmengen erhralten.

Ich mach mal ein Beispiel:

L1 = {abc} L2={xy}

L1 |_|_| L2 = {abcxy, abxcy, axbcy, xabcy, abxyc, axbyc, axybc, xabyc, xaybc, xyabc}

[chrisblablub]

Hi,

kann mir jemand erklären, wie ich nen DEA minimiere? Und zwar mit dem verfahren, wo man inne tabelle die nicht äquivalenten zustände oder so eintragen muss. Ich verstehe nicht, nach welchem Prinzip genau man da vorgeht. Konkret spreche ich von Aufgabe 39 in Serie 9. Wäre sehr nett

[MaoDelinSc]

Jo DEA Minimierung, epsilon-NEA in NEA und NEA in DEA umwandeln sind in den Folien ziemlich scheiße erklärt...

Wenn das jemand, der's drauf hat, an ein, zwei Beispielen erläutern könnte, wär das echt cool

[Taschi]

Nach meiner Erinnerung so:
1. Entferne alle Zustände die vom Startzustand nicht erreicht werden können (macht Sinn, oder? ^^)

2. Die Idee ist nun äquivalente Zustände zu finden und zu streichen. Da es leichter ist festzustellen, welche nicht äquivalent sind tun wir das und zwar dynamisch, wenn mich nicht alles täuscht. Zwei Zustände sind nicht äquivalent, wenn ein Eingabewort existiert, sodass von dem einen Endzustand durch lesen dieses Eingabeworts ein Endzustand erreicht wird, von dem anderen aus mit dem selben Eingabewort jedoch nicht. Dieses Wort ist ein trennendes Wort.
Insbesondere sind also alle Zustandspaare p und q nicht äquivalent, für die gilt, dass p ein Endzustand ist, q jedoch nicht, da dann beim Einlesen von von p aus ein Endzustand erreicht wird, von q aus jedoch nicht. Also ist hier ein trennendes Wort.
Außerdem sind alle Zustände p und q nicht äquivalent für die ein Wort w existiert, sodass von p und q zwei nicht-äquivalente Zustände erreicht werden, oder wie es auf den Vorlesungsfolien steht:
p ist äquivalent zu q gdw.

Das nutzen wir aus und damit wir uns merken könne, welche nichtäquivalenten Zustände wir schon gefunden haben schreiben wir die in eine Tabelle. Die Zeilen der Tablle stehen für die Zustände 1 bis n, die Spalten für die Zustände 0 bis n-1. Alles oberhalb der Diagonale brauchen wir nicht betrachten, da diese Relation symmetrisch ist und jeder Zustand natürlich äquivalent zu sich selbst ist. In Zelle i,j wollen wir nun das Wort schreiben, dass die Zustände i und j trennt. Um einen einfach Start zu haben schauen wir uns erstmal die Zeilen und Spalten der Endzustände an. In einer Zeile eines Endzustandes können wir an jeder Stelle als trennendes Wort eintragen, wo die zugehörige Spalte zu einem Nicht-Endzustand gehört.
Nun gehen wir immer wieder alle leeren Felder der Tabelle durch und betrachten die jeweiligen Zustandspaare. Wir wenden bei jedem Zustandspaar für jeden Buchstaben aus die zugehörige Transition an und schauen, in welchen beiden Zuständen wir landen.
Sind diese beiden Zustände nicht äquivalent sind auch die Zustände aus denen wir kamen nicht äquivalent und wir können als trennendes Wort die Kombination des benutzen Buchstaben + das trennende Wort der beiden erreichten Zustände eintragen.
Oder formal:

Wir tragen also aw in die entsprechend Zelle der Tabelle ein.
Wir gehen die Tablle solange immer wieder durch und überprüfen ob wir neue trennende Wörter finden, bis wir einmal die komplette Tabelle überprüft haben und keine neuen trennenden Wörter gefunden haben.
Die Felder die nun noch leer sind geben die äquivalenten Zustände an.
Auf Folie 16.22 sind das die Felder 0,3 und 1,4 es ist also Zustand 0 äquivalent zu Zustand 3 und Zustand 1 ist äquivalent zu Zustand 4.

Nun fassen wir die äquivalenten Zustände zusammen und zeichnen den neuen Automaten.



NEA in DEA umwandeln geht soweit ich mich erinnere über die Erreichbarkeitsmengen. Jede einzelne Erreichbarkeitsmenge gibt dann einen Zustand an, zusätzlich muss noch die leere Menge als Senke eingebaut werden. Wenn das nicht reicht schreib ich evtl. später nochmal was dazu...

[LonliLokli]

Gib's eine endliche Sprache L, die nicht kontextfrei ist?

Intuitiv nein:
Halt wenn es n Wörter in L gibt, macht man n Ableitungsregeln für die n jeweilige Wörter. Aber wie begründet man sowas formal?
Diese Antwort reicht doch nicht als Lösung in der Klausur.

[aRo]

hm, also recht hast du. Und ich würde auch beinahe sagen, dass das als Begründung reicht, wenn man das noch ein bisschen schöner (formaler) aufschreibt.

Hat jemand ne Idee woher ich gute Übungsaufgaben mit Lösungen kriege? Bisher habe ich noch eine Klausur gefunden (SS2002) allerdings leider auch ohne Lösungen. Bei s-inf und der Fachschaft habe ich geschaut

[fw]

Gib's eine endliche Sprache L, die nicht kontextfrei ist?.

Nein, jede endliche Sprache ist regulär. Es lässt sich sofort ein trivialer (Kreisfreier) endlicher Automat angeben.

[scttytrmn]

aus der vorlesung gabs ja den satz

kontextfrei => regulaer

mit negation der implikation erhaelt man ja

nicht regulaer => nicht kontextfrei

waere ja irgendwie komisch wenns so waere, weil dann braeuchte man das PL fuer kontextfreiheit garnicht - wenn gefragt wird, ob ne sprache kontextfrei ist, nimmt man einfach das PL fuer regulariaet (was einfacher ist) und wennse nich regulaer is isse auch net kontextfrei... (nur wenn man dann rauskriegt das sie regulaer ist heisst es nicht das sie kontextfrei ist schon klar, dann muesste man das andere PL auch anwenden)

[Lanchid]

aus der vorlesung gabs ja den satz

kontextfrei => regulaer

mit negation der implikation erhaelt man ja

nicht regulaer => nicht kontextfrei

Es ist genau anders herum:


Und genau deshalb funktioniert das, was du dir überlegt hast nicht...

Das kann man sich daran verdeutlichen, dass es zu jeder regulären Sprache eine rechtslineare Grammatik gibt, und diese offensichtlich kontextfrei ist (eine Art Greibach-Normalform); umgekehrt lässt sich aber nicht zu jeder kontextfreien Sprache ein regulärer Ausdruck/ein endlicher Automat finden, z.b. für , da benötigt man einen Kellerautomaten, da man die Anzahl der a's zählen muss.

[aRo]

hi!

Vorlesung 17, Folie 5 sowie 12. Was genau ist ?
Das muss auf Folie 4 irgendwie ersichtlich sein..ist es für mich aber leider nicht recht.

[LonliLokli]

hi!

Vorlesung 17, Folie 5 sowie 12. Was genau ist ?
Das muss auf Folie 4 irgendwie ersichtlich sein..ist es für mich aber leider nicht recht.

War das nicht Minimalautomat?

[aRo]

Achja...das ist das Ding das nach der Minimierung rauskommt. Danke

[LonliLokli]

Abschlusseigenshaften der gelernten Formalisen:
(Hat jemand vielleicht eine übersicht?)
als Anfang:
Reg. Ausdrucke:
Sind K,L reg. Ausdrucke, dann sind wieder Reg.Ausdrucke.

Bei den KFG sind auf jeden Fall unter Komplement nicht abgeschlossen(KSG sind das bestimmt auch mit den Argumenten aus Serie 4).

Wie sieht es aus bei Sprachen, die von Petrinetzen bzw. von PushDownAutomanten erkannt werden?

[aRo]

hi!

Richtig. NEAs, DEAs, reguläre Ausdrücke und alles was dazu gehört sind abgeschlossen unter den Booleschen Operatoren.

Kontextfreie Grammatiken sind unter Konkatenation und Vereinigung abgeschlossen, jedoch nicht unter Durchschnitt und Komplement.
Da PDAs genau die kontextfreien Grammatiken erkennen, gilt für sie wohl das selbe.

Petrinetze:
Die durch Petrinetze erkannten Sprachen liegen alle in den Kontextsensitiven, soweit ich weiß, für die gilt laut Wikipedia (haben wir das so behandelt?):
Abgeschlossen unter:
# Vereinigung,
# Konkatenation,
# Komplementbildung,
# Durchschnitt

Dann gilt das wohl auch für Petrinetze?
Was mich gerade wundert, ist, dass Wikipedia das mit der Komplementbildung behauptet. Denn die CF sind Teilmenge der Kontextsensitiven. Und wenn CF nicht unter Kompl.bildung abgeschlossen ist, wie können es dann die CS sein?

Hat von euch jemand diesen ganzen Kram mit den Sequenzdiagrammen verstanden? Ich hänge da leider ab der Semantik und den Fehlständen fest. Kann das jemand erklären?
Und noch was: Wieso ist das mit den Teilern eine partielle Ordnung, die ist doch nicht irreflexiv?

Dankeschön.