Voir la source de Universalité d'un langage rationnel

Ce développement montre que le problème d''''universalité d'un langage rationnel''' ( est-ce que <math>L = \Sigma^*</math> ? ) est PSPACE-complet. Pour des raisons de temps le caractère PSPACE peut être admis ou mis dans le plan.

== Le développement ==
pdf : [[Fichier:Pb Universalité.pdf | "Problème d'universalité"]]

== Recasements ==
* 909 - Langages Rationnels. Exemples et applications. ( pour cause d'utilisation abusive des expressions rationnelles)
* 915 - Classes de Complexité: exemples.
* (913 - Machines de Turing. Applications.) 
* ?

== Références ==
* Floyd-Biegel
* Poly cours Cachan complexité (L3) par Serge Haddad


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