Problème de séparation par automate : Différence entre versions

De AgregmathKL
Aller à : navigation, rechercher
m (unification de PSA et Problème de séparation par automates)
 
(6 révisions intermédiaires par 3 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
On montre que le problème de séparatation de langages par automates (PSA) est NP-Complet.
+
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 ==
 
== Version de Kévin 2012 ==
 
Séparons les langages
 
Séparons les langages
  
*[[Fichier:Tex.png|alt=Tex|link=|24px]] [[Média:dvt_psa.tex | Problème de séparation par automates]]
+
*[[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 automates]]
+
*[[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]]

Version actuelle en date du 27 mars 2015 à 12:52

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

PSA est NP-complet

Version de Kévin 2012

Séparons les langages

Recasements :