algorithm - 如何合并两个自动机?
问题描述
我想创建一个自动机主管。我已经能够创建自动机类。然而,当我面临合并到自动机的情况时,我不知道如何处理它。例如,使用以下自动机:
我正在使用的数据是
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)
完整代码可以在 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
我正在检查amit 在这里谈到的应用 de-morgan 的想法。但我从未实施过。无论如何,我对任何合并的想法持开放态度。
构建自动机的最少代码:
如果你需要它,这里是代码。它构建自动机但尚未合并它们:
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()
运行时它会返回:
这不是我所期望的......
解决方案
这个任务有一个更好的算法。我们想要创建一个函数,它以两个有限状态自动机作为参数并返回它们的并集。
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/
推荐阅读
- wpf - WPF一些字母比TextBlock中的其他字母大
- javascript - Ramda中函数的反向布尔返回
- java - 超类对对象的强制转换是如何工作的?
- angularjs - 更改语言 - 屏幕变白
- kubernetes - 临时存储垃圾收集
- python - paho.mqtt.client 订阅后收不到消息
- javascript - Chart.js 如何获取 X 轴的最小值-最大值?
- python - MinMaxScaler + 具有数值和分类数据的决策树分类器
- angular - ngFor 在现有应用程序中不工作,将在新创建的应用程序中工作
- node.js - 从 URL 获取对象属性值