Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Grammatik aus Sprache herleiten (http://www.informatikerboard.de/board/thread.php?threadid=1367)
Geschrieben von Mexican-Stand-off am 17.01.2013 um 16:32:
Grammatik aus Sprache herleiten
Meine Frage:
Hallo,
bin auf diesem Gebiet noch ziemlich unbewandert:
Also die Aufgabe lautet zur folgenden Sprache:
L= { a^n b^n+1 | n>=0} eine Grammatik herleiten.
Meine Ideen:
Kann ich die Regeln so festsetzen:
S-> AXB |b
A-> aA |epsilon
B-> bB | "
X-> abb | "
Danke im Vorraus.
Geschrieben von Karlito am 17.01.2013 um 17:02:
Hallo,
das funktioniert leider nicht. Alleine mit der A-Regel kannst du beliebig viele "a" erzeugen.
Angenommen Du hättest die Aufgabe, die Sprache a^n b^n zu erzeugen, wie würdest du das Lösen?
VG,
Karlito
Geschrieben von kostano am 17.01.2013 um 17:42:
also bei a^n b^n würd ich
S->aSb |ab
anwenden.
ich muss doch bei meiner aufgabe immer ein b mehr als a erzeugen. also aSbb geht ja dann auch nicht. hmm sorry, blick da so noch nicht ganz durch...
Geschrieben von kostano am 17.01.2013 um 18:07:
also würd denn
S->aSb
Sb->bb
klappen? Danke für die Gedult...
Geschrieben von Karlito am 17.01.2013 um 18:13:
Hallo,
das klappt für n = 0 nicht. Im Grunde genommen brauchst du doch als Ausgang nur b und ansonsten (a^n b^n) b...
VG,
Karlito
Forensoftware: Burning Board, entwickelt von WoltLab GmbH