Nerode- oder Pumping Lemma

Question

Hallo,

ist die Sprache L1 := {a^(2n)b^(3n) | n ≥ 0} regulär? Wenn Ja oder Nein wie kann ich sowas mit Puming oder Nerode Lemma beweisen?

LG

Answer 1

Die Sprache ist nicht regulär. Das kann man mit dem Pumping-Lemma zeigen. Das Wort uvw kann so gewählt werden, dass uv = a^m für ein m ∈ ℕ ist.

Allgemein ist eine Sprache dann nicht regulär, wenn der Automat beliebig große Zahlen zählen müsste. In der Sprache {a²ⁿb³ⁿ | n ≥ 0} muss der Automat zählen, wie lang das a^m-Präfix ist, um dann an der richtigen Stelle des b^p-Suffixes in den Erfolgszustand überzugehen.

Im Gegensatz dazu ist die Sprache {a³ⁿb^5m | n,m ≥ 0} regulär. In dieser Sprache ist die konkrete Anzahl von a und b nicht releveant, sondern nur ob diese durch 3 bzw. 5 teilbar sind. Dazu braucht nur gezählt werden, wie groß die Divisionsreste sind. Und diese sind kleiner als 3 bzw. 5.