Seite 1 von 1

Reguläre Sprachen verknüpfen

Verfasst: 1. Sep 2011 00:25
von -py-
Hallo,
kann mir jemand erklären, wie man zwei reguläre Sprachen verknüpft (Durchschnitt, Vereinigung)? Also ich habe zum Beispiel folgende Verknüpfung und ich soll einen regulären Ausdruck dazu angeben:

\(L_0 := L\big((a+b)^*aa(a+b)^*\big) \cap L\big((a+b)^*bb(a+b)^*\big)\) (Aufgabe aus Klausur WS04/05)

Ich hab dazu nirgendwo eine Erklärung gefunden, hab ich was übersehen?

Gut zu wissen wäre auch Differenz, also z.B.:

\(L_1 := L\big(((a+b)(a+b))^*\big) \setminus L\big(a^*\big)\)

Re: Reguläre Sprachen verknüpfen

Verfasst: 1. Sep 2011 06:06
von arne.lottmann
Ich glaube nicht, dass wir dazu irgendwann mal ein Schema hatten… außer man konstruiert zu beiden Sprachen den Automaten, bildet davon den Schnittautomaten und versucht, von dem wieder den Ausdruck abzulesen. Sonst bleibt einem eigentlich nur Nachdenken als Lösungsweg… Bei deinem Beispiel hilft es, sich zu überlegen, dass die erste Sprache irgendwo 'aa' hat und die zweite irgendwo 'bb'. Der entsprechende Ausdruck hieße dann [((a+b)*aa(a+b)*bb(a+b)*) + ((a+b)*bb(a+b)*aa(a+b)*)].
Beim Komplement ginge das ganze ähnlich; man muss hier sicherstellen, dass z.B. a* nicht akzeptiert wird. Das leere Wort geht eh nicht wegen (a+b), also muss man nur noch "nur a's" ausschließen. Das macht man, indem man irgendwo ein b verlangt, also: (a+b)(a+b)*b(a+b)*.
Ne bessere Lösung fällt mir aber auch nicht ein, d.h. bei komplexeren Sprachen wäre ich ziemlich aufgeschmissen :p.