Prouver que le complément de

Je veux prouver que le complément de $\{0^n1^n \mid n \geq{} 0\}$ n'est pas régulier en utilisant des propriétés de fermeture.

Je comprends que le lemme de pompage peut être utilisé pour prouver que $\{0^n1^n \mid n \geq{} 0\}$ n'est pas une langue régulière. Je comprends également que les langues régulières sont fermées en fonctionnement complémentaire. Cependant, cela implique-t-il également que le complément d'une langue non régulière est également non régulier?

formal-languages regular-languages closure-properties anthony34234
la source

Réponses:

Oui. Étant donné que le complément d'une langue régulière est également une langue régulière, il s'ensuit que le complément d'une langue non régulière doit également être non régulier. Strictement parlant, cela fonctionne puisque le complément est son propre inverse.

Patrick87
la source

Pour le dire explicitement, la preuve irait dans ce sens: vers une contradiction, soit L le complément du langage donné. Si L était régulier alors le complément de L, qui est la langue donnée:

{0^{n} 1^{n} ∣ n \geq 0}

$\{0^n 1^n \mid n \geq 0\}$ , serait également régulier par la propriété de la fermeture des langues régulières au cours de l'opération de compliment. Par conséquent, L n'est pas régulier.

JustAnotherSoul