Informatiker Board | Theoretische Informatik | sprachen unter vereinigung abgeschlossen

Informatiker Board » Themengebiete » Theoretische Informatik » sprachen unter vereinigung abgeschlossen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

sprachen unter vereinigung abgeschlossen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

infostudi
Grünschnabel

Dabei seit: 21.10.2007
Beiträge: 4

sprachen unter vereinigung abgeschlossen

Zitatantwort auf diesen Beitrag erstellen

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:23

Nehmen Sie infostudi in Ihre Freundesliste auf

kiste
Mitglied

Dabei seit: 06.05.2007
Beiträge: 29

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:38

Nehmen Sie kiste in Ihre Freundesliste auf

infostudi
Grünschnabel

Dabei seit: 21.10.2007
Beiträge: 4

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 14:48

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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:11

Nehmen Sie Tobias in Ihre Freundesliste auf

infostudi
Grünschnabel

Dabei seit: 21.10.2007
Beiträge: 4

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 15:38

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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 16:38

infostudi
Grünschnabel

Dabei seit: 21.10.2007
Beiträge: 4

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 17:08

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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?

28.10.2007 18:53

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » sprachen unter vereinigung abgeschlossen