Reguläre Sprachen verknüpfen

-py-
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mär 2011 00:27

Reguläre Sprachen verknüpfen

Beitrag von -py- » 1. Sep 2011 00:25

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)\)

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Reguläre Sprachen verknüpfen

Beitrag von arne.lottmann » 1. Sep 2011 06:06

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.

Antworten

Zurück zu „Archiv“