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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge
C3P0	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.
biker9	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