Ist für einen beliebigen DFA A := [img]
http://mokrates.de/cgi-bin/texstring?(Z%2C%5CSigma%2CK%2Cz_0%2CZ_%7Bend%7D)[/img]
Z eine Äquivalenz-Relation? Wenn ja wie sieht dann die Menge [img]
http://mokrates.de/cgi-bin/texstring?%5C%7B%5Bz%5D%7Cz%20%5Cin%20Z%5C%7D[/img] aus?
Allgemeiner: Was macht aus einer Menge zB. B := {a,b} eine Relation, so das man eine Komposition C von B mit B bilden kann?
(edit: Topictitel – fal)
Z ist die menge der Zustände, oder täusche ich mich da?
also einfach so Z = {z1,z2,z3,..}
und Relationen kannst du beliebig erstellen - jedes Kreuzprodukt aus beliebigen mengen kann als Relation angesehen werden… - beim DFA is K eine Teilmange von Z x [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma[/img] x Z , wobei dann Z x [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma[/img] -> Z die Relation ist.
das ist mir klar, aber ich habe ja nicht nach K gefragt.
Eine Antwort auf meine Frage habe jetzt selber gefunden, jede Menge ist eine 1-stellige Relation. Aber den Sprung von B := {a,b} zu B* = {a,b,aa,ab,ba,bb,…} kann ich noch nicht ganz nachvollziehen.
Eine Antwort auf meine Frage habe jetzt selber gefunden, jede Menge ist eine 1-stellige Relation.
Ja. Aber Äquivalenzrelationen sind nach Definition immer 2-stellig.
Aber den Sprung von B := {a,b} zu B* = {a,b,aa,ab,ba,bb,…} kann ich noch nicht ganz nachvollziehen.
(Da fehlt ein \lambda)
Du meinst, warum man das den "reflexiven, transitiven Abschluss" nennt? B* ist gerade so definiert, dass für 2 Wörter w_1 und w_2 jeweils auch w_1w_2 drin ist (deshalb transitiv), und dass für w_1 immer ein w_2 drin ist, so dass w_1w_2 = w_1 ist (deshalb reflexiv). Direkt mit Relationen hat das aber AFAICS nichts zu tun.
ok, ich habe meinen fehler entdeckt, ich dachte B* wäre nur für Relationen definiert, die Def. für Mengen hab ich jetzt erst im Skript wiedergefunden.
Wo finde ich die Def. von [z], z ∈ {a,b}. Ich finde nur die Def. für die Äquivalenzrelation.
Wo wird das [z] denn benutzt? Kann ich mich gar nicht dran erinnern.
Kapitel 4.3
4.16 Theorem
zu einem DFA A := (Z,Σ,z_0,Z_end) wird eine CFG G_R := (V_N,V_T,P,S) gebildet, mit V_N := {[z] | z ∈ Z}
das ist nur ein symbol, ein name… [z] ist einfach des Nonterminal was früher einen Zustand beschrieb. Einfach mit dem Ziel dass man mit Terminalen und Nonterminalen nicht durcheinander kommt.
also wenn du im DFS Z = {z1,z2,z3} hattest, hast du nun V_N = {[z1],[z2],[z3]}.
wenn im automat dann eine relation
(z1 x a x z2) war (also eine verbindung von z1 nach z2 mit dem eingabebuchstaben a)
in den produktionen also sowas:
[z1] -> a[z2]
also aus dem nonterminal [z1] wird a[z2]
Achso. Die [] haben keine besondere Bedeutung. [z] ist einfach ein Nonterminalsymbol. Genausogut hätte es auch [img]
http://mokrates.de/cgi-bin/texstring?%5Ctilde%7Bz%7D[/img] heissen können.
genau das wollte ich sagen *g*
