Automat konstruieren
-
Hey Leute!
Ich hab hier wieder eine Sprache gegeben:
L={w aus ∑*Bool | (w mod 3 = 0) ν (w = v00 mit v aus ∑*Bool)}
Erste Frage zur Sprache. Der erste Teil der Eigenschaft der Sprache, bedeutet doch, dass das eingegebene Wort, also quasi der Zahlwert, gerade durch 3 teilbar sein muss. Der zweite Teil ist klar. Was bedeutet nun das oder in der Eigeschaft der Sprache? Ich hab mir für die Konstruktion nun folgendes Überlegt:
Ich konstruiere erst zwei Automaten für die beiden Eigenschaften und füge die zwei einzelnen Automaten dann durch Kreuzprodukt-Konstruktion zusammen. Leider hab ich das bisher immer nur für Schnittmenger, Vereinigung bzw. Differenz gemacht. Geht das dann auch bei einem "logischen und" für zwei Teilsprachen?
-
vip@r schrieb:
Ich konstruiere erst zwei Automaten für die beiden Eigenschaften und füge die zwei einzelnen Automaten dann durch Kreuzprodukt-Konstruktion zusammen. Leider hab ich das bisher immer nur für Schnittmenger, Vereinigung bzw. Differenz gemacht. Geht das dann auch bei einem "logischen und" für zwei Teilsprachen?
Da gibt es einen Zusammenhang.
A u B = {x | (x in A) v (x in B)}
-
Ohja genau!
Ich schlussfolgere also mal daraus, dass dann A ∩ B = {x | (x in A) 'und' (x in B)} ist. Zugleich sollte dann auch für dies Sprache L die Kreuzprodukt-Konstruktion sinn machen, oder?
-
Naja oben steht 'v', also logisches Oder. Ich hab keine Ahnung, wie man da den entsprechenden Automaten konstruiert, aber du meintest, du könntest das
-
Naja ich mein die Vereinigungsmgen, A υ B = {x | (x in A) v (x in B)} so definiert ist, dann ist ja quasi, die Menge A (das wär dann quasi die Menge der akzept. Zustände des Automaten der ersten Eigenschaft) verodert mit der Menge B (das wär dann quasi die Menge der akzept. Zustände des Automaten der zweiten Eigenschaft). Und da diese Beziehung eben gilt, denke ich, darf ich auch mit dem üblichen Kreuzprodukt-Verfahren den neuen Automaten bauen...
-
Wie lange nehmt ihr dieses Thema eigentlich durch?
vip@r schrieb:
Naja ich mein die Vereinigungsmgen, A υ B = {x | (x in A) v (x in B)} so definiert ist, dann ist ja quasi, die Menge A (das wär dann quasi die Menge der akzept. Zustände des Automaten der ersten Eigenschaft) verodert mit der Menge B (das wär dann quasi die Menge der akzept. Zustände des Automaten der zweiten Eigenschaft).
Das sind nicht Mengen akzeptierender Zustände. Das sind Sprachen.
Und da diese Beziehung eben gilt, denke ich, darf ich auch mit dem üblichen Kreuzprodukt-Verfahren den neuen Automaten bauen...
Wie geht denn diese Konstruktion?
-
Wie diese Konstruktion geht?
Naja den Startzustand ergeben die beiden Startzustände der beiden kleinen Automaten. Der nächste Zustand ergibt sich wenn man z.b. mit der gleichen Eingabe z.B. 0 in beiden Automaten startet und dann schaut in welchen Zuständen man rauskommt und das halt so lange bis man komplett durch is...
-
vip@r schrieb:
Wie diese Konstruktion geht?
Naja den Startzustand ergeben die beiden Startzustände der beiden kleinen Automaten. Der nächste Zustand ergibt sich wenn man z.b. mit der gleichen Eingabe z.B. 0 in beiden Automaten startet und dann schaut in welchen Zuständen man rauskommt und das halt so lange bis man komplett durch is...
Ich hab mal ne kleine Aufgabe für dich, die dir bestimmt helfen wird: Erkläre nochmal die Kreuzproduktkonstruktion, aber ohne "z.B." zu sagen. Denn so, wie es jetzt da steht, hast du erklärt, was man bei einem Spezialfall macht, und selbst das versteht man noch nicht.