Automates à états

Automates

• L'état au moment t est s(t).
• Les sorties sont une fonction de l’état s et de l’entrée i :
  

  OUT(s,i)

• L’état au moment t+ε est une fonction de l’état actuel et de l’entrée
  

  s(t+ε) = NEXT(s(t), i(t), ε)

• Pour les automates non-déterministes les fonctions OUT et NEXT sont des relations.

Automates discrets

• Un automate discret change de l’état soudainement, à des moments discrets de temps.
• Nous pouvons parler de l’état suivant et de la sortie actuelle :
  

  NEXT(s,i), OUT(s,i)

Automates à états finis

• Un automate à états finis est un automate discret avec un nombre fini d’états.
• Les lecteurs de bande utilisés dans la théorie d’automates sont des dispositifs périphériques.
• Nous développons des logiciels pour des automates à états finis.
  Nous ne devons pas nous préoccuper des autres.
• Nous voyons un automate déterministe à états finis comme une paire de fonctions :

  Sortie (OUT)

  • domaine: l’ensemble de couples ordonnés (état, condition d’entrée)
  • image: l’ensemble de valeurs possibles de sortie

  EtatSuivant (NEXT)

  • domaine: l’ensemble de couples ordonnés (état, condition d’entrée)
  • image: l’ensemble d’états possibles
• Parfois il est représenté sous forme d’une simple fonction avec l’image étant un ensemble de couples (état, valeur).
• Un cycle d’interprétation a lieu à des moments discrets de temps lorsqu’un nouvel état et une nouvelle valeur sont choisis.
• Une description "clear box" d’un automate à états finis spécifie ces fonctions.
• Pour de petits automates il est commode de les représenter par des tables.

  Exemple : accepteur de ABA

  NEXT	A	B	C
  1	3	1	1
  2	3	1	1
  3	3	2	1

  OUT	A	B	C
  1	0	0	0
  2	1	0	0
  3	0	0	0

  
  
• Le même exemple avec les noms d'état mnémoniques :

  NEXT	A	B	C
  rien	a	rien	rien
  ab	a	rien	rien
  a	a	ab	rien

  OUT	A	B	C
  rien	0	0	0
  ab	1	0	0
  a	0	0	0

Équivalence d'états

Deux états sont équivalents si leurs sorties sont les mêmes et leurs états suivants sont équivalents.

Exemple :

3 et 4 sont équivalents.

Exemple :

Exercice

Construisez l’accepteur de ABA ou BAB (il devra produire 1 chaque fois lorsque ABA est reconnu, 2 lorsque BAB est reconnu et rien dans les autres cas).

Description d’automates à états finis à l’aide de prédicats

NEXT: {((‘s, i), s’) |
    (i = A ∧ s’ = 3) ∨
    ((((i = B) ∧ (‘s ≠ 3)) ∨ (i = C)) ∧ (s’ = 1)) ∨
    ((i = B) ∧ (‘s = 3) ∧ (s’ = 2)) }
OUT: {(‘s, i), out) |
    (i = A ∧ ‘s = 2 ∧ out = 1) ∨ (¬(i = A ∧ ‘s = 2) ∧ out = 0) }

Les prédicats peuvent être utilisés pour tester l’implémentation.

Modes

• Les automates à états finis réels contiennent trop d’états pour utiliser de telles méthodes.
• Il est souvent utile de regrouper des états dans des modes.

  

• Des classes de modes divisent l’ensemble d’états.
• Des modes correspondent à des partitions.
• Chaque état est exactement dans un mode pour chaque classe de modes.
• Des classes de modes sont indépendantes.
• Il est souvent utile d’avoir plus qu’une classe de modes.
• Un état peut être dans plusieurs modes mais seulement dans un mode de chaque classe.

• Modes peuvent être définis par :
  1. énumération des états membres, ou
  2. prédicat caractéristique, ou
  3. utilisation de tables décrivant la transition de modes, ou
  4. assertions sur les traces

  1. et 2. sont des "boîtes transparentes" ("clear box")
  3. et 4. sont des "boîtes noires" ("black box")
  3. n’est pas applicable de façon générale
  3. est un cas spécial de 4.
  

Exemple : table de transition de modes

Classe de mode : Fonctionnement

Modes dans la classe : Opération, Arrêt, Attente, Test

EnOp1 = @T(LimMinEau < LimiteEau < LimMaxEau) WHEN
 (Durée(EnMode(Arrêt)) < TempsVerrouillage) ∧ (TestBouton ≠ appuyé)

EnOp2 = @T(Durée(ResetBouton = appuyé) ≥ 3 s) WHEN
 (LimMinEau < LimiteEau < LimMaxEau)

EnArr = @F(DansLimites) WHEN (TestBouton ≠ appuyé)

EnAtt1 = @T(Durée(EnMode(Arrêt)) ≥ TempsVerrouillage) WHEN
 (TestBouton ≠ appuyé)

EnAtt2 = @T(Durée(EnMode(Test)) = 14 s)

EnTest = @T(Durée(TestBouton = appuyé) ≥ 500 ms)