Wird L = {a * b *} als reguläre Sprache klassifiziert?

Question

Wird L = {a * b *} als reguläre Sprache klassifiziert?

Ich bin verwirrt, weil ich weiß, dass L = {a^n b^n} nicht regelmäßig ist. Welchen Unterschied macht der Kleene Stern?

Answer 1

Nun, es macht einen Unterschied, wenn Sie eine L = {a^n b^n} und eine L = {a*b*} haben.

Wenn Sie eine a^n b^n Sprache haben, ist es eine Sprache, wo man Muss die gleiche Anzahl von a's und b's Beispiel haben: {aaabbb, ab, aabb, etc}. Wie du gesagt hast, ist das kein regulärer Ausdruck.

Aber wenn wir über L = {a*b*} sprechen ist es ein bisschen anders hier können Sie eine beliebige Anzahl von a gefolgt von einer beliebigen Anzahl von b (einschließlich 0) haben. Einige Beispiele sind:

{a, b, aaab, aabbb, aabbbb, etc} 

Wie Sie sehen, es ist anders von der {a^n b^n} Sprache, wo Sie die gleiche Anzahl von a's und b's zu haben brauchte.

Und ja a*b* ist regelmäßig von Natur aus. Wenn Sie eine gute Erklärung wollen, warum es regelmäßig ist, können Sie dies überprüfen How to prove a language is regular sie könnten eine bessere Erklärung haben dann me (:

Ich hoffe, es hat Ihnen geholfen

Answer 2

Die Sprache durch den regulären Ausdruck beschrieben ein b ist regulär per definitionem Diese Ausdrücke können keine nicht-regulären Sprachen beschreiben und stellen in der Tat eine der Möglichkeiten zur Definition der regulären Sprachen dar.

{a^nb^n: n> 0} (dies wäre ein formal vollständiger Weg von Es kann auf der anderen Seite nicht durch einen regulären Ausdruck beschrieben werden.Intuitiv, wenn Sie die Grenze zwischen a und b erreichen, müssen Sie erinnere dich an n. Da es nicht begrenzt ist, kann kein endliches Speichergerät dies tun. In einem b müssen Sie nur daran denken, dass von nun an nur b erscheinen sollte; das ist sehr begrenzt. Die beiden Sterne sind in gewissem Sinne nicht verwandt; jeder erweitert seinen Block unabhängig von dem anderen.