Se $ a $ é livre de contexto, então $ a ^ * $ é regular

Question

Atualmente estou estudando para o meu exame e estou tendo problemas para resolver esta questão:

.

certo ou errado: se $ a $ é livre de contexto, então $ a ^ * $ éregular.

Eu acho que é errado porque se $ a $ é livre de contexto, significa que $ a $ pode ser uma linguagem não regular.E os idiomas não regulares não estão fechados sob a operação da estrela de Kleene (pelo menos eu penso assim).Não tenho certeza de como escrever isso de uma maneira mais formal.

talvez assim?

Deixe $ a={a ^ nb ^ n \ mid n \ in \ mathbb {n} \} $ .Então sabemos que $ a $ não é regular e sem contexto.No entanto, não tenho certeza do que $ a ^ * $ é.

Answer 1

Deixe $ a={a ^ nb ^ n \ mid n \ in \ mathbb {n} \} $ .Então sabemos que $ a $ não é regular e sem contexto.Também podemos ver que $ a ^ * \ tampa a ^ * b ^= a $ .Como $ a ^ * b ^ * $ é uma expressão regular, sabemos que é regular.Vamos supor que um * é regular.

Os langues regulares são fechados unter interseção.Portanto $ a ^ * \ tampa a ^ * b ^ * $ deve ser também regular (porque assumimos que $ a ^* $ é regular).Isso implicaria que um é regular porque $ a ^ * \ tampa a ^ * b ^ *= A $ .Esta é uma contradição porque sabemos que um não é regular.Portanto, um * não pode ser regular.

$ q.e.d $