[FR] Quelle propriété doit être vérifiée par un automate déterministe ?

[FR] Un état utile d'un automate :

[EN] An useful state of an automaton:

[FR] Combien y a t-il d'états utiles dans l'automate ci-dessous ?

Cette question vaut 2 points.

[EN] How many useful states does the automaton below feature?

[FR] Un automate rejette un mot si et seulement si :

[EN] An automaton rejects a word if and only if:

[FR] La méthode d'élimination arrière (vue en cours) des -transitions :

[EN] The backward removal (as shown in class) of -transitions:

[FR] L'algorithme de Thompson :

[EN] Thompson's algorithm:

[FR] Soient et deux expressions régulières. Alors

[EN] Let and be two regular expressions. Then

[FR] Soit un langage rationnel, alors est récursivement énumérable.

[EN] If is a rational language, then it is also recursively enumerable.