Wykazać, że dopełnienie

12

Chcę udowodnić, że dopełnienie nie używa regularnie właściwości zamknięcia.{0n1nn0}

Rozumiem, że można użyć lematu pompującego, aby udowodnić, że nie jest zwykłym językiem. Rozumiem również, że zwykłe języki są zamknięte w ramach operacji uzupełniania. Czy to jednak oznacza również, że uzupełnienie języka nieregularnego jest również nieregularne?{0n1nn0}

anthony34234
źródło

Odpowiedzi:

9

Tak. Ponieważ dopełnienie języka regularnego jest również językiem zwykłym, to z tego wynika, że ​​uzupełnienie języka nieregularnego również musi być nieregularne. Ściśle mówiąc, działa to, ponieważ dopełniacz ma swoją własną odwrotność.

Patrick87
źródło
3
{0n1nn0}