algorithm - 如何合并两个自动机？

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
        )
    )

我正在修改以创建边缘自动机的方法是:

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)

可以找到完整的代码on 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

我正在检查在其上应用 de-morgan 的想法 that amit talked about here .但我从未实现过。无论如何，我对任何合并想法持开放态度。

构建自动机的最少代码:

如果你需要，这里是代码。它构建自动机但尚未合并它们:

    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/