aki*_*kim 13
有几种算法可以执行这项任务:Brzozowski和Mc Cluskey的"状态消除方法",线性方程组的解析,McNaughton和Yamada的方法等.它们在自动机和理性表达式中有很好的描述.作者:Jacques Sakarovitch.
特别是状态消除方法很容易理解.关键的想法是你要构建一个由理性(也就是常规)表达而不是字母标记的自动机.首先,确保您有一个初始状态和一个最终状态(如果需要,您可以添加新状态和自发转换).然后选择要消除的状态s,如下图所示的状态1.
然后考虑所有的夫妇(p,q),其中p是前任(转换到s的状态,图中的0)和qa后继(状态2).对于每个这样的对(p,q),添加从p到q的过渡,其由E(p,q)+ E(p,s)标记E(s,s)*E(s,q)其中E(p) ,s)表示"标记从p到s的转换的表达式.一旦你处理完所有的对(p,q),删除状态s.在前面的例子中:
这样做直到你消除了所有内部状态(即保持初始状态和最终状态),并且只读取从初始状态到最终状态(这里是d + ab*c)的转换结果.
你可以使用Vcsn来玩这个算法,Vcsn是一个理性表达式和自动机的工具.以下是您可以在Vcsn Sandbox中重现的完整示例.
