Wenn $ A $ Context-frei ist, dann ist $ a ^ * $ regelmäßig

Question

Ich studiere derzeit für meine Prüfung und ich habe Probleme, diese Frage zu lösen:

rechts oder falsch: Wenn $ A $ Context-frei ist, dann $ A ^ * $ istregelmäßig.

Ich denke, es ist falsch, denn wenn $ A $ kontextfrei ist, bedeutet dies, dass $ A $ kann eine nicht reguläre Sprache sein.Und die nicht-regulären Sprachen sind nicht unter dem Kleene-Star-Betrieb geschlossen (zumindest denke ich also).Ich bin nicht sicher, wie ich das in einen formellen Weg schreibt.

vielleicht so?

lass $ a={a ^ nb ^ n \ mid n \ in \ mathbb {n} \} $ .Dann wissen wir, dass $ A $ nicht regelmäßig und kontextfrei ist.Ich bin mir jedoch nicht sicher, was $ A ^ * $ ist.

Answer 1

lass $ a={a ^ nb ^ n \ mid n \ in \ mathbb {n} \} $ .Dann wissen wir, dass $ A $ nicht regelmäßig und kontextfrei ist.Wir können auch sehen, dass $ A ^ * \ CAP A ^ * B ^ *= A $ .Da $ a ^ * b ^ * $ ein regulärer Ausdruck ist, wissen wir, dass es regelmäßig ist.Nehmen wir an, dass ein * regelmäßig ist.

Die regulären Sprachen sind mit der Unterkreuzung geschlossen.Daher $ a ^ * \ cap a ^ * b ^ * $ muss auch regelmäßig sein (weil wir davon ausgehen, dass $ A ^* $ ist regelmäßig).Dies würde sich impliziert, dass A regelmäßig ist, weil $ A ^ * \ CAP A ^ * B ^ *= A $ .Dies ist ein Widerspruch, weil wir wissen, dass A nicht regelmäßig ist.Daher kann ein * nicht regelmäßig sein.

$ q.e.d $