sprachen unter vereinigung abgeschlossen

28.10.2007, 14:23

infostudi

sprachen unter vereinigung abgeschlossen

hallo,

kann mir jemand sagen, wie ich folgendes beweise:
(ich finde im internet sonst nur, dass es einfach zu beweisen wäre, irgends steht aber, wie!)

zu zeigen: alle durch grammatiken beschreibbare sprachen sind unter vereinigung abgeschlossen, d.h. für zwei beliebige sprachen und deren grammatiken L1 = L(G1) und L2 = L(G2) existiert eine Grammatik G12, so dass L(G12) = L1 U L2.

das muss irgendwie über L(G12) ist teilmenge von L1 U L2 und L1 U L2 ist Teilmenge von L(G12) zu zeigen sein.

kann mir jemand helfen, ich weiß nämlich nicht wie ich ansetzen muss oder was ich genau zeigen muss.

danke

28.10.2007, 14:38

Auf diesen Beitrag antworten »

kiste

Das lässt sich leicht konstruktiv beweisen.
Seien $[latex]G_i = (N_i,\Sigma ,P_i ,S_i)[/latex]$ mit i=1..2 die beiden Grammatiken.
o.B.d.A gilt $[latex]N_1 \cap N_2 = \varnothing[/latex]$ .

Dann ist $[latex]G = (N,\Sigma ,P,S)[/latex]$ mit $[latex]N = N_1 \cup N_2 \cup \{S\}[/latex]$ und $[latex]P = P_1 \cup P_2 \cup \{S\to S_1 | S_2\}[/latex]$ die Grammatik die die Vereinigung von L(G1) und L(G2) beschreibt.

28.10.2007, 14:48

Auf diesen Beitrag antworten »

infostudi

danke erstmal,

ich versuche das mal nachzuvollziehen:

das G1 bzw. G2 die jeweiligen Grammatiken sind ist klar. Hatte ich schon so hingeschrieben.

N1 geschnitten N2 = leere Menge:
heißt das, dass es keine Nonterminalsymbole gibt, die sowohl Element N1 als auch Element N2 sind?!

G ist dann wohl die Grammatik G12
Warum ist N dann = N1 U N2 U {S} - also insbesondere warum U {S}? N1 und N2 ist klar. {S}, da man ein unabhängiges Startsymbol braucht?

P = P1 U P2 U {S --> S1|S2} bedeutet, dass S entweder auf S1 oder auf S2 abgebildet wird?

Warum ist dass dann die Vereinigung L(G1) und L(G2) - das ist eigentlich der Schritt, an dem es momentan bei mir hängt.

28.10.2007, 15:11

Auf diesen Beitrag antworten »

Tobias

Die Nichtterminalsymbole von G1 und G2 sollen disjunkt sein, damit sich die Regeln nicht gegenseitig ins Gehege kommen.

Einfaches Beispiel:

G1 enthalte die Regel S -> Sa | Epsilon

G2 enthalte die Regel S -> b

Dann ist bei der Vereinigung der Regeln das Wort ba herleitbar, was aber nicht in der Vereinigung der Sprachen ist. Man kann aber o.B.d.A. annehmen, dass die Nichtterminalsymbole in G1 paarweise zu den Nichtterminalsymbolen in G2 verschieden sind (denn wenn das nicht so wäre, dann könnte man sie umbenennen ohne die erzeugte Sprache zu verändern).

S ist ein neues Startsymbol für die Grammatik, die die Vereinigung erzeugt.

Der Hase läuft hier so:

Zu zeigen: $[latex]w \in L(G) \iff w \in L(G_1) \cup L(G_2)[/latex]$

$[latex]w \in L(G) \iff S \to \begin{cases}S_1 \to^\ast w & \text{falls } w \in L(G_1)\\ S_2 \to^\ast w & \text{falls } w \in L(G_2)\end{cases}[/latex]$

28.10.2007, 15:38

Auf diesen Beitrag antworten »

infostudi

ich versuche dann mal eure beiden antworten zusammenzufassen.

ihr könntet mir dann vielleicht nochmal sagen, ob ich das als beweis so schreiben kann.

Es sei G1 = (N1, Sigma, P1, S1) und G2 = (N2, Sigma, P2, S2)

Da G1 und G2 disjunkt sein sollen gilt o.B.d.A. N1 geschnitten N2 = leere Menge.

G12 = (N12, Sigma, P12, S12)

mit N12 = N1 U N2 U {S12} und P12 = P1 U P2 U {S12 --> S1 | S2}

also G12 = (N1 U N2 U {S12}, Sigma, P1 U P2 U {S12 --> S1 | S2}, S12)

zu zeigen: w E L(G12) <--> w E L(G1) U w E L(G2)

w E L(G12) <--> S --> {S1 -->* w falls w E L(G1)
S2 -->* w falls w E L(G2)

und das wiederum entspricht der Vereinigung von L(G1) und L(G2).

q.e.d.

was ist eigentlich damit, dass man bei gleichheit eigentlich zeigen muss, dass das eine teilmenge vom anderen und umgekehrt ist?

tut mir übrigens leid, dass ich das hier ohne latex schreibe, aber immer wenn ich latex-code verwende hängt sich mein browser auf.
ich hoffe ihr könnt das auch so lesen und mir schnell bescheid geben, ob das so stimmt. ich muss das morgen nämlich abgeben.

danke!!!

28.10.2007, 16:38

Auf diesen Beitrag antworten »

Tobias

Zitat:

Da G1 und G2 disjunkt sein sollen gilt o.B.d.A. N1 geschnitten N2 = leere Menge.

Wann sind denn G1 und G2 disjunkt? Warum sollen sie disjunkt sein?

Zitat:

und das wiederum entspricht der Vereinigung von L(G1) und L(G2).

Was? Der Beweis der Mengengleichheit entspricht der Vereinigung?

Zitat:

was ist eigentlich damit, dass man bei gleichheit eigentlich zeigen muss, dass das eine teilmenge vom anderen und umgekehrt ist?

Genau das tust du hier:
Für Gleichheit $[latex]L(G) = L(G_1) \cup L(G_2)[/latex]$ musst du beide Inklusionsrichtungen zeigen:
$[latex]L(G) \subseteq L(G_1) \cup L(G_2)[/latex]$
$[latex]L(G) \supseteq L(G_1) \cup L(G_2)[/latex]$

$[latex]L(G) \subseteq L(G_1) \cup L(G_2)[/latex]$ entspricht aber dem:
$[latex]w \in L(G) \Rightarrow w \in (L(G_1) \cup L(G_2))[/latex]$

$[latex]L(G) \supseteq L(G_1) \cup L(G_2)[/latex]$ entspricht:
$[latex]w \in (L(G_1) \cup L(G_2)) \Rightarrow w \in L(G)[/latex]$

Fasst man beide Fälle zusammen gilt:

$[latex](w \in L(G) \iff w \in (L(G_1) \cup L(G_2))) \iff L(G) = L(G_1) \cup L(G_2)[/latex]$

28.10.2007, 17:08

Auf diesen Beitrag antworten »

infostudi

Zitat:

Original von Tobias

Zitat:

Da G1 und G2 disjunkt sein sollen gilt o.B.d.A. N1 geschnitten N2 = leere Menge.

Wann sind denn G1 und G2 disjunkt? Warum sollen sie disjunkt sein?

sie sind disjunkt, wenn alle elemente verschieden sind und dass soll so sein, da G1 und G2 unterschiedliche grammatiken sind.

Zitat:

und das wiederum entspricht der Vereinigung von L(G1) und L(G2).

Was? Der Beweis der Mengengleichheit entspricht der Vereinigung?

hab ich abgeändert. hatte geschrieben: und das (also das was in der großen geschweiften klammer steht) wiederum entspricht einem wort w E (L(G1) U L(G2))

Zitat:

was ist eigentlich damit, dass man bei gleichheit eigentlich zeigen muss, dass das eine teilmenge vom anderen und umgekehrt ist?

danke, habe ich noch ergänzt und auch verstanden!!!

28.10.2007, 18:53

Auf diesen Beitrag antworten »

Tobias

Zitat:

sie sind disjunkt, wenn alle elemente verschieden sind und dass soll so sein, da G1 und G2 unterschiedliche grammatiken sind.

Und was sind Elemente der Grammatik?

Neue Frage »

Antworten »

sprachen unter vereinigung abgeschlossen

Verwandte Themen