Voir la source de Problème de séparation par automate

On montre que le problème de séparatation de langages par automate (PSA) est NP-Complet.

== PSA est NP-complet ==
*[[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:PSA est NPcomplet.pdf|PSA est NP-complet]]
*[[Fichier:tex.png|alt=Pdf|link=|24px]] [[Média:PSA est NPcomplet.tex|PSA est NP-complet]]

== Version de Kévin 2012 ==
Séparons les langages

*[[Fichier:Tex.png|alt=Tex|link=|24px]] [[Média:dvt_psa.tex | Problème de séparation par automate]]
*[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_psa.pdf | Problème de séparation par automate]]

Recasements :
* [[908 -- Automates Finis, exemples et applications]]
* [[909 -- Langages rationnels. Exemples et applications.]]
* [[915 -- Classes de complexité : exemples.]]

[[Category: Développement de la leçon 908]]
[[Category: Développement de la leçon 909]]
[[Category: Développement de la leçon 915]]
[[Category: Développement de la leçon 928]]