Les Automates

Automates vers expression réguliere methode equations aux etats :

[pic 1]

                        1b)

[pic 2]

[pic 3]

Automates vers expression réguliere methode equations aux chemins :

[pic 4]

Avec-e :                                                sans-e :

[pic 5][pic 6]

Forme tabulaire avant détermination :                        Forme t        tabulaire après détermination[pic 7]

[pic 8]

Lemme d’Itération :[pic 9]

        Expression régulière vers automates :

        ((b · c · d + e) · (a * · d * + b · d *)) * :

[pic 10]

                                Minimisation :[pic 11]

Simplification équations : b · d · d + (a ∗ + b · c · d + e) · (a ∗ · d ∗ + b · d ∗) + a + · d+ +e) ∗ · (b · c · d) ∗         

        = ((b · c · d + e) · (a ∗ · d ∗ + b · d ∗)) ∗          

• Soit A un automate complet sur un alphabet Σ :

A est tel que son exécution est définie pour chaque mot de Σ∗

• “Tous les langages réguliers satisfont le lemme de l’itération” : vrai

• Soit L un langage régulier quelconque. Rappel : L ⊂ L 0 si L ⊆ L 0 et L 6= L :

On peut utiliser le lemme de d’itération sur L.

On peut trouver un automate d’´états fini déterministe qui reconnait L.

On peut trouver un automate d’´états finis non d´déterministe qui reconnait L.

•  Soit L un langage obtenu par la différence entre deux langages réguliers L1 et L2 quelconques (L = L1 \ L2). Rappel : |L| dénote le cardinal du langage L :

              Le contient le langage vide.

              L est un langage régulier.

• Un automate complet déterministe dont tous les états sont accepteurs reconnait le langage universel.

Vrai. L’exécution de tout mot est définie et termine dans un état accepteur

•  La différence de deux langages réguliers est un langage régulier.

Vrai. Pour deux langages réguliers E, F quelconques, E \ F = E ∩ F. D’après la fermeture des langages réguliers par les opérations de complémentation et d’intersection, nous obtenons que E \F est régulier.

• Il est possible que des langages non-réguliers satisfassent le lemme de l’itération.

Vrai. Le lemme de l’itération est satisfait par tous les langages réguliers. Rien n’est indiqué pour les langages non-réguliers.

• Il est possible que l’entier naturel 0 soit la constante d’itération d’un langage.

Vrai. Considérons le langage vide (qui est régulier), le lemme de l’itération s’applique pour N = 0. Le langage ne contient aucun mot, donc le lemme de l’itération s’applique pour tout mot du langage de longueur supérieure ou ´égale `à 0.

...