kontextsensitive Sprachen

15.04.2007, 14:24

Pampelmuse

kontextsensitive Sprachen

Hallo Info Checker,
hab hier eine Frage zu folgender Aufgabe :
Zeige das die Klasse der kontextsensitiven Sprachen abgeschlossen bzgl. konkatenation ist:

So also Vorschlag:
"Weiß nicht ob meine Schreibweise korrekt ist (bitte hier um korrektur)"

So ist A(G_0)=A (die von G_0 erzeugte Sprache)
G_0(N_a,T,S,P) sei kontextsensitiv

B(G_1)=B
G_1(N_b,T,S,P) sei kontextsensitiv

Wobei N_a =! N_b bzw. disjunkt

Sei nun A und B in CS

und
C(G_2)=CS
G_2(N_c,T,S,P) sei kontextsensitiv

mit P:
S-->AB

Somit ist auch AB in CS.
=> Somit ist die Klasse der kontextsensitiven Sparache abgeschlossen unter Konkatenation.

16.04.2007, 11:42

Auf diesen Beitrag antworten »

Tobias

Deine Idee ist m.E. richtig. An der Formulierung können wir noch arbeiten.

Zuerst einmal hättest du zumindest für uns hier erwähnen können, dass es sich bei G_0 bzw. G_1 um Grammatiken handelt mit Nichtterminalsymbolen, Terminalsymbolen, ...
Dann musst du aufpassen, welche Symbole du in die Tupel schreibst. Denn am Ende nennst du die Produktionsregel "S-->AB" wobei A und B garkeine Nichtterminale sondern Sprachen sind. Außerdem lässt du bei G_2 in der Luft hängen, was N_c, ... ist.

Zuletzt fällt mir das auf:

Zitat:

Wobei N_a =! N_b bzw. disjunkt

"Ungleich" und "disjunkt" sind zwei verschiedene Eigenschaften von Mengen. Diese Eigenschaft bezieht sich nicht auf irgendetwas. Sie müssen hier immer disjunkt sein.

Also Vorschlag:

[latex]G_0 = (N_0, T_0, S_0, P_0)[/latex]

[latex]G_0 = (N_0, T_0, S_0, P_0)[/latex]

[latex]G_1 = (N_1, T_1 S_1, P_1)[/latex]

[latex]G_2 = (N_2, T_2, S_2, P_2)[/latex]

mit:

$[latex]N_0 \cap N_1 = \emptyset \;, \; N_2 = N_0 \cup N_1 \cup \{ S_2\}[/latex]$
$[latex]T_2 = T_0 \cup T_1[/latex]$
$[latex]P_2 = P_0 \cup P_1 \cup \{S_2 \to S_0S_1 \}[/latex]$

D.h. die Grammatik G_2 setzt sich aus den Produktionsregeln und Symbolen der Grammatiken G_0 und G_1 zusammen. Hinzugefügt wird eine Konkatenation-Startproduktion. Man kann auch erwähnen, dass N_0 und N_1 o.B.d.A. disjunkt sind (denn man kann ja beliebig umbenennen).

16.04.2007, 13:09

Auf diesen Beitrag antworten »

Pampelmuse

Gut aufgegriffen ,
hab disjunkt und ugleich geschrieben da ich mir nicht sicher war ob es tatsählich das selbe bedeutet.

Bei mir haperts noch mit der Schreibweise,Danke für die Verbesserung.

Gibt es hier auch ein Formeleditior? , ich weiß wie man Code einfügt aber nicht wie man ihn schreibt.

Ich muß doch noch zeigen das G_0,G_1,G_2
kontextsensitiv :
Bei G_0,G_1 krieg ich es noch selbst hin.

G_O(N_0,T_0,S_0,P_0) mit
P_0:
a_0 N_0 b_0--> a_0 x_0 b_0
|a_0 N_0 b_0|-->| a_0 x_0 b_0|
mita_0, x_0, b_0 element (N_0 Vereinigung T_0)* wobei x_0\ epsilon also nicht leer.
Somit ist G_0 kontextsensitiv.
Dies kann ich analog mit G_1 machen

Aber bei G_2 hab ich das Problem :
S-->S_0 S_1

Hier ist doch S ein Terminal oder?
Aber es muß doch mind. ein Nichtterminal links stehen oder?

16.04.2007, 16:49

Auf diesen Beitrag antworten »

Tobias

Bei G_0 und G_1 musst du garnichts zeigen. Du nimmst als Voraussetzung zwei beliebige kontextsensitive Sprachen A und B. Diese Sprachen werden von den kontextsensitiven Grammatiken G_0 und G_1 erzeugt. Jetzt musst du zeigen, dass auch die Sprache AB von einer kontextsensitiven Grammatik erzeugt werden kann. Die neue Grammatik konstruierst du dir aus allen Produktionsregeln aus G_0 und G_1. Das ist natürlich immernoch kontextsensitiv. Dann fügst du noch die Startproduktion hinzu:

S_2 -> S_0S_1 wobei S_0 und S_1 die STARTSYMBOLE! aus G_0 und G_1 sind.

16.04.2007, 18:24

Auf diesen Beitrag antworten »

Pampelmuse

Ich hab ja oben P_0 und P_1 definiert,

Soll ich nun einfach
P: P_0
P: P_1
P: S-->S_0 S_1

=> G_2 ist eine kontextsensitive Grammatik ?

16.04.2007, 18:56

Auf diesen Beitrag antworten »

Tobias

Ich versteh deine Notation nicht. Ich hab dir doch schon P_2 definiert. Wo ist das Problem?

16.04.2007, 19:00

Auf diesen Beitrag antworten »

Pampelmuse

Ich dachte man muß noch zeigen das P_2 kontextsensitiv ist.
Danke Tobias

16.04.2007, 22:12

Auf diesen Beitrag antworten »

Tobias

Also kontextsensitiv ist eine Grammatik. Das hängt natürlich dann mit den Produktionsregeln zusammen.

Wir wissen, dass P_0 und P_1 Regeln sind, die mit einer kontextsensitiven Grammatik konform gehen. Nun haben wir $[latex]P_2 = P_0 \cup P_1 \cup \{S_2 \to S_0S_1 \}[/latex]$ ergänzt. D.h. die einzige Regel, die wir noch verifizieren müssen ist $[latex]S_2 \to S_0S_1[/latex]$ . Das sind die Startsymbole (also Nichtterminale) der entsprechenden Grammatiken. Das ist natürlich bei kontextsensitiven Grammatiken so erlaubt (das ist sogar bei Kontextfreien Grammatiken erlaubt).

Also ist G_2 eine kontextsensitive Grammatik. Die erzeugte Sprache ist gerade die Konkatenation aller Wörter aus L(G_0) mit denen aller Wörter aus L(G_1).

Neue Frage »

Antworten »

kontextsensitive Sprachen

Verwandte Themen