Kontextsensitive Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:45 Do 29.07.2010 | | Autor: | dawu |
Hallo Matheräum'ler,
ich lerne gerade für meine Zwischenprüfung in theoretischer Informatik und habe eine Verständnisfrage bezüglich kontextsensitiver (k.s.) Sprachen/Grammatiken. Ich habe diese Frage in keinem anderen Forum gestellt. Also:
Die Sprache
[mm]L_1 = \{ a^nb^nc^n\ |\ n \geq 1 \}[/mm]
ist kontextsensitiv, das habe ich schon vielerorts gelesen. Leider habe ich so meine Probleme mit dem "natürlichen" Verständnis der Definition k.s. Grammatiken. Ich möchte jetzt nicht die Definition und die Regeln von [mm]L_1[/mm] abtippen, man kann beides ![[]](/images/popup.gif) hier nachlesen.
In meinem Buch steht als "saloppe" Erklärung, dass bei k.s. Sprachen das Ersetzen von Nichtterminale durch Terminale abhängig vom Kontext ist, was mit bei der o. g. Sprache [mm]L_1[/mm] auch einleuchtet. Dies wird dadurch zum Ausdruck gebracht, dass ich nicht einfach alle [mm]A,B,C \in N[/mm] durch [mm]a,b,c \in T[/mm] ersetzen kann, sondern prüfen muss, an welcher Stelle diese stehen (Regeln 5-8 im Wikipedia-Eintrag).
In unserem Skript ist nun die Sprache
[mm]L_2 = \{ 0^n1^n0^n\ |\ n \geq 1 \}[/mm]
angegeben, dort steht (ohne Erklärung), dass diese nicht kontextsensitiv sei. Jetzt ist meine Frage, warum dies -- im Vergleich zu [mm]L_1[/mm] -- der Fall ist?
Auch hier ist das Ersetzen von Nichtterminalen analog zu [mm]L_2[/mm] abhängig vom Kontext, deshalb verstehe ich es nicht wirklich...
Wäre nett, wenn mir jemand helfen könnte.
Viele Grüße,
dawu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:45 Do 29.07.2010 | | Autor: | felixf |
Moin dawu!
> ich lerne gerade für meine Zwischenprüfung in
> theoretischer Informatik und habe eine Verständnisfrage
> bezüglich kontextsensitiver (k.s.) Sprachen/Grammatiken.
> Ich habe diese Frage in keinem anderen Forum gestellt.
> Also:
>
> Die Sprache
>
> [mm]L_1 = \{ a^nb^nc^n\ |\ n \geq 1 \}[/mm]
>
> ist kontextsensitiv, das habe ich schon vielerorts gelesen.
> Leider habe ich so meine Probleme mit dem "natürlichen"
> Verständnis der Definition k.s. Grammatiken. Ich möchte
> jetzt nicht die Definition und die Regeln von [mm]L_1[/mm] abtippen,
> man kann beides
> hier
> nachlesen.
Das ist ja ein schoenes Beispiel, Regel 1 verletzt Punkt 4 der Produktionsregeln (unter Definition auf der selben Seite) :) Aber das ist nicht so tragisch, das kann man durch Einfuehren eines Hilfsnichtterminals umgehen, das macht das ganze nur etwas umstaendlicher...
> In meinem Buch steht als "saloppe" Erklärung, dass bei
> k.s. Sprachen das Ersetzen von Nichtterminale durch
> Terminale abhängig vom Kontext ist, was mit bei der o. g.
> Sprache [mm]L_1[/mm] auch einleuchtet. Dies wird dadurch zum
> Ausdruck gebracht, dass ich nicht einfach alle [mm]A,B,C \in N[/mm]
> durch [mm]a,b,c \in T[/mm] ersetzen kann, sondern prüfen muss, an
> welcher Stelle diese stehen (Regeln 5-8 im
> Wikipedia-Eintrag).
Genau.
> In unserem Skript ist nun die Sprache
>
> [mm]L_2 = \{ 0^n1^n1^n\ |\ n \geq 1 \}[/mm]
>
> angegeben, dort steht (ohne Erklärung), dass diese nicht
> kontextsensitiv sei. Jetzt ist meine Frage, warum dies --
> im Vergleich zu [mm]L_1[/mm] -- der Fall ist?
Nun, diese Sprache ist sehr wohl kontextsensitiv, sie ist sogar kontextfrei! Man beginnt mit dem Startsymbol S und den Regeln
$S [mm] \to [/mm] 0 N 11$
$N [mm] \to \varepsilon$
[/mm]
$N [mm] \to [/mm] 0 N 11$
(Hier sind $S$ und $N$ Nichtterminalsymbole.)
Dann bekommt man genau die Woerter aus deiner Sprache hin, da diese gleich [mm] $\{ 0^n 1^{2 n} \mid n \ge 1 \}$ [/mm] ist.
Bist du dir sicher, dass du die Sprache richtig wiedergegeben hast? Andernfalls ist das Skript da wohl falsch...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:55 Sa 31.07.2010 | | Autor: | dawu |
Hi Felix,
danke für deine Antwort! Natürlich hast du wieder Recht und ich mich bei den ganzen Eigenschaften verwirren lassen. Die Sprache ist natürlich nicht kontextfrei.
Ich kann ja mal versuchen, dir die Grammatik zu geben. Eigentlich müsste diese ja der Grammatik von [mm]L_2[/mm] sehr ähnlich sein:
1. [mm]S & \rightarrow 0SBC\ |\ 0BC [/mm]
2. [mm]CB \rightarrow BC [/mm]
3. [mm]0B \rightarrow 01 [/mm]
4. [mm]1B \rightarrow 11 [/mm]
5. [mm]1C \rightarrow 10 [/mm]
6. [mm]0C \rightarrow 00 [/mm]
In unserem Skript ist das ganze länger, aber mir erscheinen diese Regeln sehr plausibel. Zumindest kann ich so Worte aus [mm]L_2[/mm] erstellen.
Die Regeln für kontextsensitive Sprachen dürfen laut unserem Skrip nur die Form [mm]xXy \rightarrow xzy[/mm], wobei [mm]x,y,z \in (N \cup T)^*[/mm] und [mm]X \in N[/mm] ([mm]N[/mm] sind Nichtterminale, [mm]T[/mm] Terminale).
Jetzt erkenne ich einfach nicht, wo, in Bezug auf die Definition der Kontextsensitivität, der Unterschied zwischen [mm]L_1[/mm] und [mm]L_2[/mm] ist.
Viele Grüße,
dawu
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Di 03.08.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
Es geht mir nur um die Kontextsensitivität.
