En théorie du calcul en informatique quel est le complément du langage ?


En informatique, le terme "langage" est spécifique et technique.

Partez d'un ensemble fini quelconque et considérez l'ensemble de toutes les listes possibles de ses éléments (y compris la liste vide). Le terme technique pour le premier ensemble est l'"alphabet" et le second ensemble est l'ensemble des "chaînes de caractères" sur cet alphabet.


Bien que nous appelions cela un "alphabet", il n'est pas nécessaire que ce soit des lettres. Il peut littéralement être n'importe quel ensemble fini.

Un "langage" sur un alphabet est tout sous-ensemble de l'ensemble des chaînes sur cet alphabet. Une classe importante de problèmes théoriques implique des programmes qui décident si une chaîne donnée est membre d'un langage donné.

Puisqu'un langage n'est rien de plus qu'un sous-ensemble d'un ensemble particulier, il devrait maintenant être évident que le complément du langage n'est rien de plus que son complément en tant qu'ensemble - l'ensemble des chaînes qui ne sont pas dans le langage.

Le complément d'un langage est aussi un langage, et déterminer l'appartenance au complément est essentiellement le même problème que de déterminer l'appartenance au langage original.