Développement : Séparation par automate NP-complet

Détails/Enoncé :

Input : k entier et S,T deux langages finis.
Output : Existe t'il un automate A à k états qui sépare S et T.
Ce problème est NP-complet.

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :

Références utilisées dans les versions de ce développement :

Le Langage des machines, Floyd, Beigel (utilisée dans 7 versions au total)