Trouver un automate de produit direct (fini déterministe) en Python

Aperçu

Trouvez l'automate produit direct. Utilisez automata-lib pour gérer les automates finis déterministes en python.

pip install automata-lib

J'ai fait référence à l'article suivant. Implémenter un automate fini déterministe en Python pour déterminer des multiples de 3

environnement

python 3.8 windows 10

Je pense que n'importe quoi dans le 3ème système fonctionnera probablement.

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():
    #Automate qui accepte les multiples de 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'}
    )
    #Automate qui accepte les multiples de 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'}
    )
    #Accepter les multiples de 2 et 3=Automate qui accepte les multiples de 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()

Un petit commentaire

La fonction SYMBOL_FORMAT définit les conventions de dénomination des états. La fonction directproduct est la principale caractéristique de cet article. C'est aussi simple que de calculer chaque paramètre tel que défini. Je voudrais savoir s'il existe l'algorithme le plus rapide.

La fonction principale est exécutée en trouvant l'automate produit direct "automate qui accepte les multiples de 6" de "automate qui accepte les multiples de 3" et "automate qui accepte les multiples de 2".

Exemple d'exécution

Input number > 18
Result: Accepted

Puisque 18 est un multiple de 6, il sera accepté.

Input number > 15
Result: Rejected

15 n'est pas un multiple de 6 et ne sera pas accepté.