0 Daumen
379 Aufrufe

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

Avatar von

1 Antwort

0 Daumen

Die Sprache ist nicht regulär. Das kann man mit dem Pumping-Lemma zeigen. Das Wort uvw kann so gewählt werden, dass uv = am 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 {a2nb3n | n ≥ 0} muss der Automat zählen, wie lang das am-Präfix ist, um dann an der richtigen Stelle des bp-Suffixes in den Erfolgszustand überzugehen.

Im Gegensatz dazu ist die Sprache {a3nb5m | 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.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community