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)
--- zeigen, dass keine reguläre sprache - pumping lemma (http://www.informatikerboard.de/board/thread.php?threadid=934)
Geschrieben von biker9 am 01.05.2011 um 13:52:
zeigen, dass keine reguläre sprache - pumping lemma
Hallo,
ich hadere gerade an folgendem Problem:
L = {a^m b^n | m != n}
Ich möchte zeigen, dass L nicht regulär ist, finde aber keinen Ansatz..
Wenn m = n gilt, dann ist es einfach..
Vielleicht kann mir jemand helfen,
Danke
Geschrieben von C3P0 am 04.05.2011 um 14:37:
RE: zeigen, dass keine reguläre sprache - pumping lemma
Hallo,
nimm mal an, dass L regulär ist. Dann gibt es einen endlichen Automaten, der L akzeptiert. Dieser Automat habe k Zustände. Mit dem Wort a^k kommt man dann bei wenigstens einem Zustand zweimal vorbei, man läuft also einen Kreis der Länge
. Jetzt müsste der Automat das Wort
akzeptieren. Daraus kannst du einen Widerspruch erhalten.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH