Informatiker Board | Theoretische Informatik | zeigen, dass keine reguläre sprache

Informatiker Board » Themengebiete » Theoretische Informatik » zeigen, dass keine reguläre sprache - pumping lemma

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

zeigen, dass keine reguläre sprache - pumping lemma

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

biker9
Grünschnabel

Dabei seit: 01.05.2011
Beiträge: 1

zeigen, dass keine reguläre sprache - pumping lemma

Zitatantwort auf diesen Beitrag erstellen

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

01.05.2011 13:52

Nehmen Sie biker9 in Ihre Freundesliste auf

C3P0
Grünschnabel

Dabei seit: 04.05.2011
Beiträge: 4

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 $[latex] l \geq 1 [/latex]$ . Jetzt müsste der Automat das Wort $[latex]a^k b^{k-l}[/latex]$ akzeptieren. Daraus kannst du einen Widerspruch erhalten.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von C3P0: 04.05.2011 20:59.

04.05.2011 14:37

Nehmen Sie C3P0 in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » zeigen, dass keine reguläre sprache - pumping lemma