Problème de séparation par automate : Différence entre versions
De AgregmathKL
| Ligne 8 : | Ligne 8 : | ||
Recasements : | Recasements : | ||
| − | |||
* [[908 -- Automates Finis, exemples et applications]] | * [[908 -- Automates Finis, exemples et applications]] | ||
* [[909 -- Langages rationnels. Exemples et applications.]] | * [[909 -- Langages rationnels. Exemples et applications.]] | ||
* [[915 -- Classes de complexité : exemples.]] | * [[915 -- Classes de complexité : exemples.]] | ||
| − | |||
[[Category: Développement de la leçon 908]] | [[Category: Développement de la leçon 908]] | ||
[[Category: Développement de la leçon 909]] | [[Category: Développement de la leçon 909]] | ||
[[Category: Développement de la leçon 915]] | [[Category: Développement de la leçon 915]] | ||
Version du 26 février 2015 à 21:16
On montre que le problème de séparatation de langages par automate (PSA) est NP-Complet.
Version de Kévin 2012
Séparons les langages
Recasements :
