Implémenter un automate fini déterministe en Python pour déterminer des multiples de 3

La bibliothèque automata-lib facilite l'implémentation d'automutons en Python.

Que faire dans cet article

Utilisez l'automate fini déterministe en Python pour déterminer si un nombre binaire est divisible par 3. C'est un exemple que l'on trouve souvent dans les manuels. Si l'entrée est un multiple de 3, elle sera acceptée, sinon elle sera rejetée. Cela ressemble à ceci dans le diagramme de transition d'état.

Si c'est un devoir universitaire, vous devez l'implémenter vous-même, mais ici nous allons l'implémenter avec la bibliothèque automata-lib.

environnement

OS

• Pengwin 1.4.1 on WSL

Version Python

Python 3.8.1

Bibliothèque à utiliser

automata-lib automata-lib fonctionne avec Python 3.4 et supérieur.

Construire l'environnement

L'environnement a été construit avec pipenv.

$ pipenv --python 3.8
$ pipenv install automata-lib
$ pipenv shell

Exemple d'exécution

La valeur numérique d'entrée (nombre décimal) est donnée comme premier argument. S'il est divisible par 3, il sera affiché comme «Résultat: Accepté», et s'il n'est pas divisible par 3, il sera affiché comme «Résultat: Rejeté». Après cela, la transition est également sortie. C'est pratique.

Exemple accepté

$ ./modulo_three.py 12
12
Result: Accepted
Transitions
q0
q1
q0
q0
q0

Exemples de rejet

$ ./modulo_three.py 11
11
Result: Rejected
Transitions
q0
q1
q2
q2
q2
Traceback (most recent call last):
  File "./modulo_three.py", line 40, in <module>
    for i in modulo.read_input_stepwise(entry):
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
105, in read_input_stepwise
    self._check_for_input_rejection(current_state)
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
87, in _check_for_input_rejection
    raise exceptions.RejectionException(
automata.base.exceptions.RejectionException: the DFA stopped on a non-final state (q2)

La description

Définition d'automate

L'implémentation de l'automate fini déterministe utilise la classe DFA.

modulo_three.py

modulo = DFA(
    states = {'q0', 'q1', 'q2'},
    input_symbols = {'0', '1'},
    transitions = {
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q2', '1': 'q0'},
        'q2': {'0': 'q1', '1': 'q2'}
    },
    initial_state='q0',
    final_states={'q0'}
)

--state définit l'état de cet automate. --ʻInput_symbols définit les symboles d'entrée. --Définissez une règle qui passe de chaque état à un autre avec des «transitions». Par exemple, en prenant «q0» comme exemple, si l'entrée est 0, elle passera à «q0», et si l'entrée est 1, elle passera à «q1». --Spécifiez l'état de départ avec ʻinitial_state. --Spécifiez l'état d'acceptation avec final_state.

Exécuter automuton

Si vous voulez simplement déterminer si elle est acceptée, utilisez la méthode ʻaccept_input. S'il est accepté, il renvoie «True», et s'il est rejeté, il renvoie «False». Notez que l'argument de la méthode ʻaccept_input est une chaîne binaire.

>>> modulo.accepts_input('10')
False
>>> modulo.accepts_input('110')
True

Si vous voulez voir comment il transite, utilisez la méthode read_input_stepwise. Cette méthode renvoie la transition dans le générateur. S'il est rejeté, il renvoie une exception RejectionException.

Exemple accepté

>>> for i in modulo.read_input_stepwise('110'):
...   print(i)
...
q0
q1
q0
q0

Exemples de rejet

>>> for i in modulo.read_input_stepwise('10'):
...   print(i)
... 
q0
q1
q2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
105, in read_input_stepwise
    self._check_for_input_rejection(current_state)
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
87, in _check_for_input_rejection
    raise exceptions.RejectionException(
automata.base.exceptions.RejectionException: the DFA stopped on a non-final state (q2)

code

Vous pouvez le trouver ici. Licence MIT. https://github.com/bateleurX/qiita-modulo_three