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)
--- Grammatik gesucht (http://www.informatikerboard.de/board/thread.php?threadid=124)
Geschrieben von lego am 07.01.2007 um 15:24:
Grammatik gesucht
Hallo, ich habe eine Frage zu dieser Aufgabenstellung:
Sei L={a^n b^n c^n}. Man gebe eine Grammtiak an, die L* erzeugt.
Was ist in diesem Zusammenhang L*?
Hat vielleicht jemand einen Tipp für die Grammatik?
Geschrieben von Tobias am 07.01.2007 um 16:11:
Vielleicht hilft es dir, wenn ich dir sage, dass es hirfür keine kontextfreie Grammatik geben kann. (Beweis: Pumpinglemma).
Deine einzige Chance ist eine kontextsensitive Grammatik.
Geschrieben von lego am 07.01.2007 um 16:20:
Und was ist nun in diesem Zusammenhang L*? kenne * nur als Zeichen für das Monoid über..
Geschrieben von Tobias am 08.01.2007 um 02:06:
Das hatten wir doch schonmal.
L* ist die Kleenesche Hülle (freies Monoid).
![[latex]L^\ast = \bigcup_{n\in \mathbb{N}_0}L^n[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L^\ast = \bigcup_{n\in \mathbb{N}_0}L^n)
Dabei ist
![[latex]L^0 := \{ \varepsilon \}, \quad L^{n+1} := L\cdot L^{n}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L^0 := \{ \varepsilon \}, \quad L^{n+1} := L\cdot L^{n})
Forensoftware: Burning Board, entwickelt von WoltLab GmbH