Implement a deterministic finite automaton in Python to determine multiples of 3

The automata-lib library makes it easy to implement automata in Python.

What to do in this article

Use a deterministic finite automaton in Python to determine if a binary number is divisible by 3. It's an example that is often found in textbooks. If the input is a multiple of 3, it will be accepted, otherwise it will be rejected. It looks like this in the state transition diagram.

If it's a university homework, you should implement it yourself, but here we will implement it with the automata-lib library.

environment

OS

• Pengwin 1.4.1 on WSL

Python version

Python 3.8.1

Library to use

automata-lib automata-lib works with Python 3.4 and above.

Building the environment

The environment was built with pipenv.

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

Execution example

Give the input numerical value (decimal number) as the first argument. If it is divisible by 3, it will be output as Result: Accepted, and if it is not divisible by 3, it will be output as Result: Rejected. After that, the transition is also output. It's convenient.

Accepted example

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

Examples of rejection

$ ./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)

Description

Definition of automaton

The implementation of the deterministic finite automaton utilizes the DFA class.

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 defines the state of this automaton. --ʻInput_symbolsdefines the input symbols. --Define a rule that transitions from each state to another withtransitions. For example, taking q0 as an example, if the input is 0, it will transition to q0, and if the input is 1, it will transition to q1. --Specify the start state with ʻinitial_state. --Specify the acceptance state with final_state.

Running automaton

If you simply want to determine if it is accepted, use the ʻaccept_inputmethod. If it is accepted, it returnsTrue, and if it is rejected, it returns False. Note that the argument of the ʻaccept_input method is a binary string.

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

If you want to see how it transitions, use the read_input_stepwise method. This method returns the transition in the generator. If rejected, it returns a RejectionException exception.

Accepted example

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

Examples of rejection

>>> 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

You can find it here. It is an MIT license. https://github.com/bateleurX/qiita-modulo_three