Problème de séparation par automate : Différence entre versions
De AgregmathKL
| Ligne 1 : | Ligne 1 : | ||
On montre que le problème de séparatation de langages par automate (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 == | ||
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 :
