Langages et Automates

Introduction

Les automates sont des outils mathématiques essentiels pour étudier les langages formels. Ce document sert de référence pour comprendre, visualiser et appliquer les concepts des automates.

Concepts Fondamentaux

Élément

Description

Alphabet

Ensemble des symboles utilisés.

États

Positions ou conditions de l'automate.

État Initial

Point de départ du traitement.

États Acceptants

États indiquant qu'une chaîne est reconnue.

Transitions

Règles de passage d'un état à l'autre selon un symbole.

Types d'Automates

Automate Fini Déterministe (DFA)

  • Chaque paire (état, symbole) conduit à une unique transition.

Automate Fini Non Déterministe (NFA)

  • Possibilité de plusieurs transitions pour une même paire (état, symbole).

  • Peut inclure des transitions spontanées (ε-transitions).

Fonctionnement d'un Automate

  1. Initialiser à l'état initial.

  2. Lire la chaîne symbole par symbole.

  3. Appliquer la règle de transition correspondante.

  4. Accepter si l'état final atteint est un état acceptant.

Exemple de DFA

Description :
Un DFA simple avec deux états.

  • États : {q0, q1}

  • Alphabet : {a, b}

  • État initial : q0

  • États acceptants : {q1}

Tableau des transitions :

État de départ

Entrée

État d'arrivée

q0

a

q1

q0

b

q0

q1

a

q1

q1

b

q0

Minimisation d'un Automate

Méthode de Nerode

  • Identifier les états équivalents (reconnaissant le même langage).

  • Fusionner ces états pour obtenir un automate réduit.

Exemple de Minimisation avec la Méthode de Nerode

Automate initial :

État de départ

Entrée

État d'arrivée

A

0

B

A

1

C

B

0

A

B

1

D

C

0

D

C

1

A

D

0,1

D

Les états B et C étant équivalents, l'automate minimisé devient :

Automate minimisé :

État de départ

Entrée

État d'arrivée

A

0,1

X

X

0

A

X

1

D

D

0,1

D

Méthode de Moore

  • Partitionner initialement : états acceptants vs non acceptants.

  • Raffiner les partitions en fonction des transitions.

  • Reconstruire l'automate minimal à partir des partitions finales.

Exemple de Minimisation avec la Méthode de Moore

Automate initial :

État de départ

Entrée

État d'arrivée

P

a

Q

P

b

R

Q

a

P

Q

b

S

R

a

S

R

b

P

S

a,b

S

Après raffinement, les états P, Q et R se regroupent. L'automate minimal devient :

Automate minimal :

État de départ

Entrée

État d'arrivée

P'

a

P'

P'

b

S

S

a,b

S

Transformation d'un NFA en DFA

  1. Construire les sous-ensembles d'états :

    • Démarrer avec {état initial + ε-transitions}.

    • Pour chaque groupe d'états, déterminer les transitions pour chaque symbole.

  2. Ajouter un "état puit" pour les transitions indéfinies afin de compléter le DFA.