FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

Schnittmenge von 2 Sprachen

Schnittmenge von 2 Sprachen 2011-02-27 15:34
7thiesse
Hallo,

ich bin grad über etwas gestopert, wobei mir keine Methode einfällt, um es schnell zu lösen.

Gesucht ist die Schnittmenge von 2 Sprachen:
L1 = a(b+c)*b+
L2 = (ab)*c(b+c)*c(a+b)*

Ich möchte ungern alle Möglichen Wörter aufschreiben ;) Gibts da eine Vorgehensweise, die mir entfallen ist`?

Danke euch

RE: Schnittmenge von 2 Sprachen 2011-02-27 15:38
Anonymer User
TS für jede Sprache bauen
TS(LS3) konstruieren (TS(L1) Schnitt TS(L2))
Ablesen


??? :)

RE: Schnittmenge von 2 Sprachen 2011-02-27 15:45
7thiesse
perfekt, danke

RE: Schnittmenge von 2 Sprachen 2011-02-27 15:46
T4Y
Jau, in diesem Fall brauchst du das ProduktTS mit Sync = {(x,x)}.
Für den Schnitt von Omega-Sprachen nimmst du ein etwas anderes TS (das mit diesen q-Flags).
Siehe auch Skript S. 16/17

RE: Schnittmenge von 2 Sprachen 2011-02-27 22:11
Wulf
Hrm. Wenn man einen endlichen (erstmal deterministischen) Automaten hat, kann man als neue Zustandsmenge das Kreuzprodukt der Zustandsmengen bilden. Endzustände sind dann genau die, wo beide Zustände ein Endzustand waren. Dann noch unerreichbares wegstreichen und Sprache ablesen.
Ich komme da auf folgenden Automaten:
[img]https://www.fb18.de/mybb/attachment.php?aid=507[/img]
abcb*(c+b+)+
Wobei + bei mir "mind. 1x" heißt, nicht oder.
Anhänge schnitt.png