Informatiker Board | formale Sprachen | Beweise für reguläre Sprachen / Kleene Stern

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Beweise für reguläre Sprachen / Kleene Stern

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Beweise für reguläre Sprachen / Kleene Stern

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Kuerbel
Grünschnabel

Dabei seit: 26.10.2015
Beiträge: 3

Beweise für reguläre Sprachen / Kleene Stern

Zitatantwort auf diesen Beitrag erstellen

Moin,

ich sitze gerade vor folgendem Problem und ich weiss einfach nicht, wie ich die Rechenregeln anwenden darf bzw wie ein Beweis in TheoInf aufgebaut ist:

Ich soll zeigen, dass wenn L1 eine Teilmenge von L2 ist, dass L1* konkateniert mit L2* = L2* ist.

Ich meine es macht Sinn und stimmt (der Auftrag ist: zeigen oder widerlegen), aber wie zeigt man so etwas?

26.10.2015 21:24

Nehmen Sie Kuerbel in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo Kuerbel,

Du musst eine Teilmengenbeziehung in beide Richtungen zeigen. Also:
$[latex]\mathcal{L}_1^* \cdot \mathcal{L}_2^* \subseteq \mathcal{L}_2^* [/latex]$
und
$[latex] \mathcal{L}_2^* \subseteq \mathcal{L}_1^* \cdot \mathcal{L}_2^* [/latex]$

Die erste Beziehung ist etwas kniffliger (aus meiner Sicht). Man muss nachweisen, dass $[latex] \mathcal{L}_1^* \subseteq \mathcal{L}_2^* [/latex]$ und dass durch die Konkatenation mit $[latex] \mathcal{L}_2^* [/latex]$ keine Wörter hinzukommen, die nicht in $[latex] \mathcal{L}_2^* [/latex]$ enthalten sind. Dazu ist es nötig Anhand der Definition des Kleene-Sterns und der Potenzsprachen zu argumentieren.

Die zweite Beziehung ist einfach, da $[latex] \mathcal{L}_1^0 \subseteq \mathcal{L}_1^* [/latex]$ und somit $[latex] \mathcal{L}_2^* \subseteq \mathcal{L}_1^0 \cdot \mathcal{L}_2^* \subseteq \mathcal{L}_1^* \cdot \mathcal{L}_2^* [/latex]$ .

Gruß,

Karlito

29.10.2015 10:05

Nehmen Sie Karlito in Ihre Freundesliste auf

Kuerbel
Grünschnabel

Dabei seit: 26.10.2015
Beiträge: 3

Hallo,

vielen Dank für deine Hilfe. Dass $[latex]L1^* \subseteq L2^*[/latex]$ ist, habe ich schon in der vorherigen Aufgabe gezeigt. Ich habe damit argumentiert, dass wenn $[latex]w \in L1^*[/latex]$ , dann gilt $[latex]w \in L1[/latex]$ , und aus $[latex]L1 \subseteq L2[/latex]$ ergibt sich $[latex]w \in L2[/latex]$ , also auch $[latex]w \in L2^*[/latex]$

Quasi wie man bei einer ähnlichen Potenzmengenbeziehung argumentieren würde... ist das denn richtig so?

Ich glaube, ich stehe gerade ziemlich auf dem Schlauch :-(

30.10.2015 10:01

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hi,

ich glaube ich habe zu kompliziert gedacht großes Grinsen

Sei

ein Wort aus [latex]L1[/latex]

und

ein Wort aus [latex]L2[/latex]

, dann sind alle Wörter aus $[latex]L1^*\cdot L2^*[/latex]$ von der Form $[latex]u'\cdot v'[/latex]$ , wobei $[latex]u' \in L1^i . i \in \mathbb{N}[/latex]$ und $[latex]v' \in L1^j . j \in \mathbb{N}[/latex]$ .

Für i = j = 0 erhalten wir das leere Wort, welches in [latex]L2^*[/latex]

enthalten ist.
Für i = 0, j > 0 erhalten wir alle Wörter aus [latex]L2^*[/latex]

.
Für i > 0, j = 0 erhalten wir [latex]L1^*[/latex]

, was eine Teilmenge von [latex]L2^*[/latex]

darstellt.
Für i > 0, j > 0 erhalten wir Wörter der Form $[latex]u_0\dots u_nv_0\dots v_n[/latex]$ . Da alle u und alle v in L2 sind, erhalten wir lt. Definition des Kleene-Sterns Elemente der Sprache [latex]L1^*[/latex]

.

Damit sollten wir durch sein.

Gruß,

Karlito

30.10.2015 11:31

Kuerbel
Grünschnabel

Dabei seit: 26.10.2015
Beiträge: 3

Ja super, vielen Dank :-)

Langsam wird mir das auch alles klarer. Was hältst du denn von meinem Beweis oben? Reicht das aus?

30.10.2015 19:53

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ich würde es eben etwas Detaillierter machen. Also ähnlich wie bei mir im vierten Fall. Also darüber, dass es eine Konkatenation von Wörtern ist, welche in L2 enthalten sind und somit L1 eine Teilmenge von L2 ist. Dabei aber nicht das leere Wort vergessen. Dieser Randfall sollte immer mit rein.

Gruß,

Karlito

31.10.2015 01:42

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Beweise für reguläre Sprachen / Kleene Stern