Die Sprache {ww} < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:09 Do 04.06.2009 | | Autor: | DFisch- |
| Aufgabe | Geben Sie eine kontextsensitive Grammatik für die folgende Sprache an:
{w#w | w [mm] \in [/mm] {a,b}* } |
Also ich hatte zuerst die Idee, durch Regeln der Form S->aSA | bSB | #
Wörter so zu erschaffen, dass auf der linken Seite der Raute ein Wort in Terminalzeichen und auf der rechten Seite das selbe Wort gespiegelt in Nichtterminalzeichen steht und dann über Vertauschungen das Wort auf der rechten Seite zu spiegeln. Ich bin aber daran gescheitert, dass ich nicht einstellen kann, dass die Nichtterminalzeichen nur nach rechts verschoben werden dürfen.
Ich habe danach den Tipp bekommen, zuerst ein Wörter der Form aAbBbB....# zu erschaffen - also dass immer ein Terminal von einem Nichtterminal gefolgt wird und am Ende die Raute steht - und dann die Nichtterminale nach rechts zu tauschen. Aber damit kann ich überhaupt nichts anfangen - woher "weiss" denn ein Nichtterminal, wann es auf der rechten Seite am richtigen Platz angekommen ist und nicht mehr weitergetauscht werden muss?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Sa 06.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
