Beweis: Kontextsensitivität < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:00 Do 17.06.2010 | | Autor: | extasic |
| Aufgabe | | Zeigen Sie, dass die Sprache L = [mm] \{ ww | w \in \{a,b\}^\* \} [/mm] kontextsensitiv ist |
Hi!
Ich habe leider überhaupt keine Ahnung wie ich da Ansetzen soll. Eine richtige Definition oder Beispiele habe ich nicht gefunden.
Könnt ihr mir bitte sagen was ich machen muss, um die Kontextsensitivität von L zu zeigen?
Danke im Voraus!
|
|
| |
|
Hallo extasic,
> Zeigen Sie, dass die Sprache L = [mm]\{ ww | w \in \{a,b\}^\* \}[/mm]
> kontextsensitiv ist
> Hi!
>
> Ich habe leider überhaupt keine Ahnung wie ich da Ansetzen
> soll. Eine richtige Definition oder Beispiele habe ich
> nicht gefunden.
>
> Könnt ihr mir bitte sagen was ich machen muss, um die
> Kontextsensitivität von L zu zeigen?
Du könntest probieren, eine kontextsensitive Grammatik anzugeben, die die Sprache L erzeugt...
>
> Danke im Voraus!
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 07:02 Fr 18.06.2010 | | Autor: | extasic |
Das ist mir klar - die Frage ist, wie Diese aussieht..
Inzwischen bin ich weiter gekommen bzw. wir haben weitere Hilfestellungen bekommen.
Nach dem letzten Hinweis habe ich eine Grammatik mit folgender Finaler Ersetzung:
S ->* ... ->* abbXA'B'B' für das Wort ww = abbabb
Nun muss ich theoretisch ja nur noch die Nonterminale A' und B' durch die entsprechenden Nonterminale ersetzen. Mein Problem ist aber das X. Wie kann ich das genau dann kollabieren lassen, wenn alle Nonterminale ersetzt wurden (denn das ist genau noch der letzte Teil, der wir mit an die Hand bekommen haben)?
Vielen Dank im Voraus für eure Hilfe!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:20 So 20.06.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
