Beweise bei Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 01:06 Sa 28.01.2012 | | Autor: | hilado |
| Aufgabe | Im Folgenden seien L, [mm] L_1, L_2, L_3 [/mm] Sprachen über demselben Alphabet [mm] \Sigma. [/mm] Beweisen oder widerlegen Sie die folgenden Aussagen. Benennen Sie jeweils auch das Verfahren, das Sie zum Nachweis Ihrer Behauptung verwenden.
(a) [mm] L_1 [/mm] * [mm] L_2 [/mm] = [mm] L_2 [/mm] * [mm] L_1
[/mm]
(b) [mm] (L_1 [/mm] * [mm] L_2) [/mm] * [mm] L_3 [/mm] = [mm] L_1 [/mm] * [mm] (L_2 [/mm] * [mm] L_3)
[/mm]
(c) [mm] (L_1 \cap L_2) [/mm] * [mm] L_3 [/mm] = [mm] (L_1 [/mm] * [mm] L_3) \cap (L_2 [/mm] * [mm] L_3)
[/mm]
(d) [mm] L_1 \subseteq L_2, [/mm] so gilt auch [mm] L_1 [/mm] * L [mm] \subseteq L_2 [/mm] * L und L * [mm] L_1 \subseteq [/mm] L * [mm] L_2.
[/mm]
(e) [mm] (L_1 [/mm] * [mm] L_2)^R [/mm] = [mm] {L_2}^R [/mm] * [mm] {L_1}^R
[/mm]
(f) Ist [mm] L_1 \subseteq L_2, [/mm] so gilt auch [mm] L/L_1 \subseteq L/L_2.
[/mm]
(g) [mm] (L_1/L_2)*L_2 [/mm] = [mm] L_1 [/mm] |
Also ich hab leider nicht alles, weil ich zu manchen einfach nicht weiß, wie ich das am besten machen. Das sind Teil (b), (c) und (f)
Zu den anderen habe ich folgendes:
(g)
Definition von L/L': Die Quotientensprache zweier Sprachen L und L' über demselben Alphabet [mm] \Sigma [/mm] ist definiert durch: L/L' := { w [mm] \in \Sigma^{\*} [/mm] : es gibt ein u [mm] \in [/mm] L' derart, dass wu [mm] \in [/mm] L }
[mm] L_1 [/mm] = {aa, bb, cc}
[mm] L_2 [/mm] = {a, b}
[mm] (L_1 [/mm] / [mm] L_2) [/mm] = {a, b}
[mm] (L_1 [/mm] / [mm] L_2) [/mm] * [mm] L_2 [/mm] = {aa, bb} [mm] \not= L_1
[/mm]
Das wäre dann ein direkter Beweis für die Widerlegung der Aussage.
(a) [mm] L_1 [/mm] * [mm] L_2 [/mm] = { ww' [mm] \in \Sigma^{\*}, [/mm] w [mm] \in L_1, [/mm] w' [mm] \in L_2 [/mm] }
[mm] L_2 [/mm] * [mm] L_1 [/mm] = { w'w [mm] \in \Sigma^{\*}, [/mm] w [mm] \in L_1, [/mm] w' [mm] \in L_2 [/mm] }
[mm] L_1 [/mm] = {aa}
[mm] L_2 [/mm] = {bb}
[mm] L_1 [/mm] * [mm] L_2 [/mm] = {aabb}
[mm] L_2 [/mm] * [mm] L_1 [/mm] = {bbaa}
Das wäre dann auch wieder ein direkter Beweis.
(b) Ich wills mal versuchen, aber ich bin mir hier überhaupt nicht sicher:
[mm] L_1 [/mm] * [mm] L_2 [/mm] = { uv [mm] \in \Sigma^{\*}, [/mm] u [mm] \in L_1, [/mm] v [mm] \in L_2 [/mm] } =: [mm] L_{12}
[/mm]
[mm] L_2 [/mm] * [mm] L_3 [/mm] = { vw [mm] \in \Sigma^{\*}, [/mm] v [mm] \in L_2, [/mm] w [mm] \in L_3 [/mm] } =: [mm] L_{23}
[/mm]
[mm] (L_1 [/mm] * [mm] L_2) [/mm] * [mm] L_3 [/mm] = [mm] L_{12} [/mm] * [mm] L_3 [/mm] = { uvw [mm] \in \Sigma^{\*}, [/mm] uv [mm] \in L_{12}, [/mm] w [mm] \in L_3 [/mm] }
[mm] L_1 [/mm] * [mm] (L_2 [/mm] * [mm] L_3) [/mm] = [mm] L_1 [/mm] * L_23 = { uvw [mm] \in \Sigma^{\*}, [/mm] u [mm] \in L_1, [/mm] vw [mm] \in L_{23} [/mm] }
=> [mm] L_{12} [/mm] * [mm] L_{3} [/mm] = [mm] L_1 [/mm] * [mm] L_{23} [/mm] =>
[mm] (L_1 [/mm] * [mm] L_2) [/mm] * [mm] L_3 [/mm] = [mm] L_1 [/mm] * [mm] (L_2 [/mm] * [mm] L_3)
[/mm]
d) [mm] L_1 \subseteq L_2, [/mm] d.h. jedes Element von [mm] L_1 [/mm] ist auch in [mm] L_2. [/mm] Durch die Konkatenation beider Mengen mit L entstehen zwei neue Mengen:
[mm] L_1 [/mm] * L = { uw, u [mm] \in L_1, [/mm] w [mm] \in [/mm] L }
[mm] L_2 [/mm] * L = { vw, v [mm] \in L_2, [/mm] w [mm] \in [/mm] L }
Wir nehmen nun an, dass die Menge [mm] L_1 [/mm] * L nun keine Teilmenge von [mm] L_2 [/mm] * L ist. D.h. wir finden mind. ein Element in der Menge [mm] L_1 [/mm] * L, dass nicht in [mm] L_2 [/mm] * L ist. D.h. wir müssen ein Element finden, für das gilt
[mm] \exists [/mm] u in [mm] uw_1 [/mm] : [mm] \forall [/mm] v in [mm] vw_2 [/mm] : v [mm] \not= [/mm] u, [mm] w_1 [/mm] = [mm] w_2
[/mm]
Das würde bedeuten, dass es mind. ein Element in [mm] L_1 [/mm] gibt, dass nicht in [mm] L_2 [/mm] liegt, doch damit wäre [mm] L_1 [/mm] nicht mehr Teilmenge von [mm] L_2 [/mm] und das ist ein Widerspruch zur Vorraussetzung, dass [mm] L_1 \subseteq L_2.
[/mm]
Der zweite Teil geht dann genauso.
(e) Def: [mm] L^R [/mm] = { [mm] w^R, [/mm] w [mm] \in [/mm] L }
w = [mm] w_1 [/mm] ... [mm] w_n
[/mm]
[mm] w^R [/mm] = [mm] w_n [/mm] ... [mm] w_1
[/mm]
[mm] (L_1 [/mm] * [mm] L_2)^R [/mm] = { [mm] {(u_1u_2)}^R [/mm] : [mm] u_1 \in L_1, u_2 \in L_2 [/mm] }
[mm] u_1 [/mm] = [mm] w_1 [/mm] ... [mm] w_n
[/mm]
[mm] u_2 [/mm] = [mm] v_1 [/mm] ... [mm] v_n
[/mm]
[mm] {u_1}^R [/mm] = [mm] w_n [/mm] ... [mm] w_1
[/mm]
[mm] {u_2}^R [/mm] = [mm] v_n [/mm] ... [mm] v_1
[/mm]
[mm] {(u_1u_2)}^R [/mm] = [mm] v_n [/mm] ... [mm] v_1 w_n [/mm] ... [mm] w_1 [/mm] = [mm] {u_2}^R {u_1}^R
[/mm]
[mm] {L_2}^R [/mm] * [mm] {L_1}^R [/mm] = { [mm] {u_2}^R {u_1}^R [/mm] : [mm] u_1 \in L_1, u_2 \in L_2 [/mm] }
=> [mm] {(L_1 * L_2)}^R [/mm] = [mm] {L_2}^R [/mm] * [mm] {L_1}^R [/mm] => Diese Aussage stimmt.
Was meint ihr zu meinen Lösungen? Sind diese auch mathematisch korrekt oder soll ich das anders machen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Mi 01.02.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
