Как объединить два автомата?

Question

Я хочу создать супервизора автоматов.Я был в состоянии создать класс автоматов.Но когда я сталкиваюсь со случаем слияния с автоматами, я не знаю, как с этим справиться.Например, со следующими автоматами:

Я использую данные

donnees=("nomprob", # name of the problem
        [("e1",True),("e2",True),("e3",True),("s1",False),("s2",False),("s3",False)], # events
        ("plant",[("S4",True,False),("S1",False,False),("S2",False,True)], # first automata states
            [("S4","S1",["e1","e2","e3"]),("S1","S2",["e1","e3"]),("S1","S4",["s1","s2","s3"]),("S2","S1",["s1","s2","s3"])]), # first automata transitions
        ("spec",[("S0",True,False),("S1",False,False),("S2",False,True)], #second automata s.t0ates
            [("S0","S1",["e1","e2","e3"]),("S1","S2",["e1","e2","e3"]),("S1","S0",["s1","s2","s3"]),("S2","S1",["s1","s2","s3"])] # second automata transitions
        )
    )

И метод, который я 'Модификация m для создания помеченных автоматов:

def creerplantspec(self,donnees):
    """method to creat the synchronised automata.

    Args:
        donnees (:obj:`list` of :obj:`str`): name, events, transition and states of the synchronisation automata.

    Attributes :
        plantspec (Automate): automata of specifications we want to create with a given name, events and states.
    """
    nom,donneesEtats,donneesTransitions=donnees
    self.plantspec=Automate(nom,self)
    for elt in donneesEtats :
        nom,initial,final=elt

        (self.spec+self.plant).ajouterEtat(nom,initial,final)
    for elt in donneesTransitions:
        nomDepart,nomArrivee,listeNomsEvt=elt
        self.spec.ajouterTransition(nomDepart,nomArrivee,listeNomsEvt)

Полный код можно найти на github .Я уже думал об этом алгоритме:

for (Etat_s, Etat_p) in plant, spec:
    we create a new state Etat_{s.name,p.name}
    for (transition_s, transition_p) in Etat_s, Etat_p:
        new state with the concatenation of the names of the ends of the transitions
        if transitions' events are the same:
            we add a transition from Etat_{s.name,p.name} to this last state
        else if transition's are different
            here I don't know

Я проверяю идеи применения к нему деморгана , о котором говорил здесь .Но я никогда не реализовывал это.В любом случае, я открыт для любых идей слияния.

Минимальный код для построения автоматов:

Если вам это нужно, вот код.Он строит автоматы, но еще не объединяет их:

    def creerplantspec(self,donnees):
        """method to create the synchronised automata.

        Args:
            donnees (:obj:`list` of :obj:`str`): name, events, transition and states of the synchronisation automata.

        Attributes :
            plantspec (Automate): automata of specifications we want to create with a given name, events and states.
        """
        nom,donneesEtats,donneesTransitions=donnees
        self.plantspec=Automate(nom,self)
        for elt in donneesEtats :
            nom,initial,final=elt

        for elt in donneesTransitions:
            nomDepart,nomArrivee,listeNomsEvt=elt
            self.spec.ajouterTransition(nomDepart,nomArrivee,listeNomsEvt)

    # we're going to synchronize
    def synchroniserProbleme(self):
        # we're saving the states of both
        etat_plant = self.plant.etats
        etat_spec = self.spec.etats
        # we create the automaton merging  plant and spec automata
        self.plantspec = Automate("synchro",self)
        print self.evtNomme
        # then we synchronize it with all the states
        for etat_p in etat_plant:
            for etat_s in etat_spec:
                self.synchroniserEtats(etat_p, etat_s, self) 


    def synchroniserEtats(self, etat_1, etat_2, probleme):
        # we're adding a new state merging the given ones, we're specifying if it is initial with all and final with any
        print str(etat_1.nom + etat_2.nom)
        self.plantspec.ajouterEtat(str(etat_1.nom + etat_2.nom), all([etat_1.initial,etat_2.initial]), any([etat_1.final, etat_2.final]))

        # 
        for transition_1 in etat_1.transitionsSortantes:
            for transition_2 in etat_2.transitionsSortantes:
                self.plantspec.ajouterEtat(str(transition_1.arrivee.nom+transition_2.arrivee.nom), all([transition_1.arrivee.nom,transition_2.arrivee.nom]), any([transition_1.arrivee.nom,transition_2.arrivee.nom]))
                # we're going to find the subset of the events that are part of both transitions
                evs = list(set(transition_1.evenements).intersection(transition_2.evenements))
                # we filter the names 
                evs = [ev.nom for ev in evs]
                # 
                self.plantspec.ajouterTransition(str(etat_1.nom+etat_2.nom),str(transition_1.arrivee.nom+transition_2.arrivee.nom), evs)

donnees=("nomprob", # name of the problem
        [("e1",True),("e2",True),("e3",True),("s1",False),("s2",False),("s3",False)], # events
        ("plant",[("S4",True,False),("S1",False,False),("S2",False,True)], # first automata states
            [("S4","S1",["e1","e2","e3"]),("S1","S2",["e1","e3"]),("S1","S4",["s1","s2","s3"]),("S2","S1",["s1","s2","s3"])]), # first automata transitions
        ("spec",[("S0",True,False),("S1",False,False),("S2",False,True)], #second automata states
            [("S0","S1",["e1","e2","e3"]),("S1","S2",["e1","e2","e3"]),("S1","S0",["s1","s2","s3"]),("S2","S1",["s1","s2","s3"])] # second automata transitions
        )
    )



nom,donneesEvts,donneesPlant,donneesSpec=donnees

monProbleme=Probleme(nom)

for elt in donneesEvts:
    nom,controle=elt
    monProbleme.ajouterEvenement(nom,controle)


monProbleme.creerPlant(donneesPlant)
monProbleme.plant.sAfficher()

monProbleme.creerspec(donneesSpec)
monProbleme.spec.sAfficher()

# my attempt
monProbleme.synchroniserProbleme()

# visualise it
# libraries

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

# Build a dataframe 

print monProbleme.plantspec.transitions

fro =  [transition.depart.nom for transition in monProbleme.plantspec.transitions if len(transition.evenements) != 0]
to = [transition.arrivee.nom for transition in monProbleme.plantspec.transitions if len(transition.evenements) != 0]

df = pd.DataFrame({ 'from':fro, 'to':to})

print fro

print to

# Build your graph
G=nx.from_pandas_edgelist(df, 'from', 'to')

# Plot it
nx.draw(G, with_labels=True)
plt.show()

И при запуске он возвращает:

Какиене совсем то, что я ожидал ...

Answer 1

Существует гораздо лучший алгоритм для этой задачи.Мы хотим создать функцию, которая принимает два конечных автомата в качестве своих параметров и возвращает их объединение.

FSA union(FSA m1, FSA m2)
    #define new FSA u1
    FSA u1 = empty
    # first we create all the states for our new FSA
    for(state x) in m1:
        for(state y) in m2:
            # create new state in u1
            State temp.name = "{x.name,y.name}"
            if( either x or y is an accept state):
                make temp an accept State
            if( both x and y are start states):
                make temp the start State
            # add temp to the new FSA u1
            u1.add_state(temp)
    # now we add all the transitions
    State t1, t2
    for (State x) in m1:
        for (State y) in m2:
            for (inp in list_of_possible_symbols):
                # where state x goes on input symbol inp
                t1 = get_state_on_input(x, inp);
                # where state y goes on input symbol inp
                t2 = get_state_on_input(y, inp);
                # add transition from state named {x.name, y.name} to state named {t1.name, t2.name}
                u1.add_transition(from: {x.name, y.name}, to: {t1.name, t2.name}, on_symbol: {inp})
    return (FSA u1)

Я выписал псевдокод для алгоритма выше.Конечные автоматы (FSA) обычно называют детерминированными конечными автоматами (DFA) и недетерминированными конечными автоматами (NFA).Интересующий вас алгоритм обычно называется алгоритмом построения объединения DFA.Если вы посмотрите вокруг, вы найдете множество готовых реализаций.

Например, отличная реализация на C: https://phabulous.org/c-dfa-implementation/