The automata-lib library makes it easy to implement automata in Python.
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.
OS
Python 3.8.1
automata-lib automata-lib works with Python 3.4 and above.
The environment was built with pipenv.
$ pipenv --python 3.8
$ pipenv install automata-lib
$ pipenv shell
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.
$ ./modulo_three.py 12
12
Result: Accepted
Transitions
q0
q1
q0
q0
q0
$ ./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)
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 with
transitions. 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
.
If you simply want to determine if it is accepted, use the ʻaccept_inputmethod. If it is accepted, it returns
True, 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)
You can find it here. It is an MIT license. https://github.com/bateleurX/qiita-modulo_three
Recommended Posts