Se $ A $ è senza contesto, allora $ a ^ * $ è regolare

Question

Attualmente sto studiando per il mio esame e sto avendo problemi a risolvere questa domanda:

.

Destra o errato: se $ A $ è senza contesto, quindi $ a ^ * $ regolare.

Penso che sia sbagliato perché se $ a $ è senza contesto, significa che $ a $ può essere un linguaggio non regolare.E le lingue non regolari non sono chiuse sotto l'operazione di Kleene Star (almeno lo penso).Non sono sicuro di come scrivere questo in modo più formale.

Forse come questo?

Let $ A={A ^ NB ^ N \ MID N \ IN \ MathBB {N} \ \ MATHBB {N} \} $ .Allora sappiamo che $ A $ non è normale e senza contesto.Tuttavia, non sono sicuro di quale $ a ^ * $ è.

Answer 1

Let $ A={A ^ NB ^ N \ MID N \ IN \ MathBB {N} \ \ MATHBB {N} \} $ .Allora sappiamo che $ A $ non è normale e senza contesto.Inoltre possiamo vedere che $ a ^ * \ cap a ^ * b ^ *= a $ .Dal momento che $ a ^ * b ^ * $ è un'espressione regolare, sappiamo che è regolare.Consente di supporre che A * sia regolare.

I linguaggi regolari sono l'intersezione chiusa Unter.Pertanto $ a ^ * \ cap a ^ * b ^ * $ deve essere anche regolare (perché assumiamo che $ a ^* $ è regolare).Ciò implicirebbe che A è regolare perché $ a ^ * \ tappo a ^ * b ^ *= a $ .Questa è una contraddizione perché sappiamo che A non è regolare.Quindi a * non può essere regolare.

$ Q.e.d $