Find (deterministic finite) Cartesian automata in Python

Overview

Find the Cartesian automaton. Use automata-lib to handle deterministic finite automata in python.

pip install automata-lib

I referred to the following article. Implement a deterministic finite automaton in Python to determine multiples of 3

environment

python 3.8 windows 10

I think that anything in the 3rd system will probably work.

code

directproduct.py

from automata.fa.dfa import DFA

SYMBOL_FORMAT = lambda s0, s1 : f'({s0}, {s1})'

def directproduct(dfa0:DFA, dfa1:DFA) -> DFA:
    new_input_symbols : set = dfa0.input_symbols | dfa1.input_symbols
    new_initial_state : str = SYMBOL_FORMAT(dfa0.initial_state, dfa1.initial_state)
    new_final_state : set = set([SYMBOL_FORMAT(f0, f1) for f0 in list(dfa0.final_states) for f1 in list(dfa1.final_states)])

    new_states : set = set()
    new_trans : dict = {}
    for s0 in list(dfa0.states):
        for s1 in list(dfa1.states):
            state = SYMBOL_FORMAT(s0, s1)
            new_states.add(state)
            new_trans[state] = {
                s : SYMBOL_FORMAT(dfa0.transitions[s0][s], dfa1.transitions[s1][s]) for s in list(new_input_symbols)
            }
    
    return DFA(
        states = new_states,
        input_symbols = new_input_symbols,
        transitions = new_trans,
        initial_state = new_initial_state,
        final_states = new_final_state
    )

def main():
    #Automata that accept multiples of 3
    modulo_three = DFA(
        states = {'a', 'b', 'c'},
        input_symbols = {'0', '1'},
        transitions = {
            'a': {'0': 'a', '1': 'b'},
            'b': {'0': 'c', '1': 'a'},
            'c': {'0': 'b', '1': 'c'}
        },
        initial_state = 'a',
        final_states = {'a'}
    )
    #Automata that accept multiples of 2
    modulo_two = DFA(
        states = {'d', 'e'},
        input_symbols = {'0', '1'},
        transitions = {
            'd' : {'0' : 'd', '1' : 'e'},
            'e' : {'0' : 'd', '1' : 'e'}
        },
        initial_state = 'd',
        final_states = {'d'}
    )
    #Accept multiples of 2 and 3=Automata that accept multiples of 6
    modulo_six = directproduct(modulo_three, modulo_two)

    print('Input number > ', end='')
    num : int = int(input())
    entry : str = format(num, 'b')
    if modulo_six.accepts_input(entry):
        print("Result: Accepted")
    else:
        print("Result: Rejected")

if __name__ == '__main__':
    main()

A little commentary

The SYMBOL_FORMAT function defines a state naming convention. The directproduct function is the main character in this article. It's as simple as calculating each parameter according to the definition. I would like to know if there is the fastest algorithm.

The main function is executed by finding the direct product automaton "automaton that accepts multiples of 6" from "automaton that accepts multiples of 3" and "automaton that accepts multiples of 2".

Execution example

Input number > 18
Result: Accepted

Since 18 is a multiple of 6, it will be accepted.

Input number > 15
Result: Rejected

15 is not a multiple of 6 and will not be accepted.