DFA für die Sprache L={a, b | |a| = |b|}

Question

Moin,

Gibt es überhaupt einen DFA für die Sprache

L = {a, b | |a| = |b|} 

?

Ich glaube, dass die nicht regulär ist, wollte aber nicht mit dem pumpinglemma Verfahren rumprobieren, weil ich da beim Anblick des Wikipedia Artikels etwas überfordert war...

Hatte schonmal jemand das Problem?
Beste Grüße

Answer 1

Die Sprache ist in meinen Augen nicht sauber definiert bzw. von der Notation her etwas ungewöhnlich.

Du meinst wahrscheinlich die Sprache \(L:=\left\{w\in\Sigma^*\mid \text{ Anzahl der }a\text{'s} = \text{ Anzahl der }b\text{'s}\right\}\), oder? Für diese Sprache wirst Du keinen DFA finden und brauchst ein "Gedächtnis". Die Sprache \(L\) ist also nicht regulär.

Zum Pumping-Lemma gibt es gute Videos auf DuRöhre: 

Comments

Haha, sorry André für die Formulierung  Du hast absolut recht, ich musste mir das etwas aus dem Gedächtnis kramen (wobei wir wieder beim Thema sind).

Vielen Dank für die Aufklärung und den Video Tipp!

---

Kein Thema! Vielen Dank für den Stern und Dein Engagement auf der Stacklounge!