Prove que o complemento de não é regular usando propriedades de fechamento

12

Quero provar que o complemento de não é regular usando propriedades de fechamento.{0n1nn0}

Entendo que o lema de bombeamento pode ser usado para provar que não é um idioma comum. Também entendo que os idiomas regulares estão fechados sob operação complementar. No entanto, isso também implica que o complemento de um idioma não regular também não é regular?{0n1nn0}

anthony34234
fonte

Respostas:

9

Sim. Como o complemento de um idioma regular também é um idioma regular, segue-se que o complemento de um idioma não regular também deve ser não regular. A rigor, isso funciona, pois o complemento é inverso.

Patrick87
fonte
3
Apenas para declarar explicitamente, a prova seria executada ao longo destas linhas: Em direção a uma contradição, seja L o complemento da linguagem especificada. Se L fosse regular, o complemento de L, que é o idioma especificado: , também seria regular, pois a propriedade dos idiomas regulares seria fechada durante a operação de elogio. . Portanto, L não é regular. {0n1nn0}
JustAnotherSoul