0 Daumen
413 Aufrufe

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

von

1 Antwort

+3 Daumen
 
Beste Antwort

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: 

von

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!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community