Finden Sie (deterministische endliche) direkte Produktautomaten in Python

Überblick

Finden Sie den direkten Produktautomaten. Verwenden Sie automata-lib, um deterministische endliche Automaten in Python zu verarbeiten.

pip install automata-lib

Ich habe auf den folgenden Artikel verwiesen. Implementierung eines deterministischen endlichen Automaten in Python zur Bestimmung von Vielfachen von 3

Umgebung

python 3.8 windows 10

Ich denke, dass alles im 3. System wahrscheinlich funktionieren wird.

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():
    #Automat, der ein Vielfaches von 3 akzeptiert
    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'}
    )
    #Automat, der ein Vielfaches von 2 akzeptiert
    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'}
    )
    #Akzeptiere Vielfache von 2 und 3=Automat, der ein Vielfaches von 6 akzeptiert
    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()

Ein kleiner Kommentar

Die Funktion SYMBOL_FORMAT definiert Statusbenennungskonventionen. Die Direktproduktfunktion ist das Hauptmerkmal dieses Artikels. Es ist so einfach wie die Berechnung jedes Parameters wie definiert. Ich würde gerne wissen, ob es den schnellsten Algorithmus gibt.

Die Hauptfunktion wird ausgeführt, indem der direkte Produktautomat "Automat, der Vielfache von 6 akzeptiert" aus "Automat, der Vielfache von 3 akzeptiert" und "Automat, der Vielfache von 2 akzeptiert" ermittelt wird.

Ausführungsbeispiel

Input number > 18
Result: Accepted

Da 18 ein Vielfaches von 6 ist, wird es akzeptiert.

Input number > 15
Result: Rejected

15 ist kein Vielfaches von 6 und wird nicht akzeptiert.