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. mod3dfa.png

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

environment

OS

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

Recommended Posts

Implement a deterministic finite automaton in Python to determine multiples of 3
How to determine the existence of a selenium element in Python
I tried to implement a card game of playing cards in Python
I tried to implement a pseudo pachislot in Python
How to develop in a virtual environment of Python [Memo]
How to get a list of built-in exceptions in python
A story about trying to implement a private variable in Python.
I tried to implement blackjack of card game in Python
Try to get a list of breaking news threads in Python.
How to check the memory size of a variable in Python
How to check the memory size of a dictionary in Python
I tried to implement a misunderstood prisoner's dilemma game in Python
I tried to implement PLSA in Python
I tried to implement permutation in Python
Display a list of alphabets in Python 3
I tried to implement PLSA in Python 2
I tried to implement ADALINE in Python
I tried to implement PPO in Python
Find (deterministic finite) Cartesian automata in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
How to send a visualization image of data created in Python to Typetalk
[Python] How to put any number of standard inputs in a list
I want to color a part of an Excel string in Python
Python code to determine the monthly signal of a relative strength investment
How to format a list of dictionaries (or instances) well in Python
I made a program to check the size of a file in Python
[Python] [Word] [python-docx] Try to create a template of a word sentence in Python using python-docx
Draw a graph of a quadratic function in Python
Try to implement Oni Maitsuji Miserable in python
How to clear tuples in a list (Python)
To execute a Python enumerate function in JavaScript
How to embed a variable in a python string
How to implement Discord Slash Command in Python
Summary of how to import files in Python 3
Get the caller of a function in Python
I want to create a window in Python
How to implement shared memory in Python (mmap.mmap)
How to create a JSON file in Python
Make a copy of the list in Python
Summary of how to use MNIST in Python
Rewriting elements in a loop of lists (Python)
A clever way to time processing in Python
How to implement a gradient picker in Houdini
Steps to develop a web application in Python
I tried to implement TOPIC MODEL in Python
To add a module to python put in Julialang
How to notify a Discord channel in Python
Make a joyplot-like plot of R in python
Output in the form of a python array
Get a glimpse of machine learning in Python
[Python] How to draw a histogram in Matplotlib
I tried to implement selection sort in python
A well-prepared record of data analysis in Python
Various ways to read the last line of a csv file in Python
How to pass the execution result of a shell command in a list in Python
A confusing story with two ways to implement XGBoost in Python + overall notes
Japanese translation of self-study "A Beginner's Guide to Getting User Input in Python"
Type in Python to implement algebraic extension (1) ~ Monoids, groups, rings, ring of integers ~
I tried to implement what seems to be a Windows snipping tool in Python
How to get a list of files in the same directory with python
Implement Enigma in python