2

我想在mathematica中创建一个模块，如果自动机是确定性的则返回。我正在考虑，如果有 2 个转换从同一状态开始并读取相同的符号，或者存在一个空转换，则自动机不是确定性的。

我想调试这段代码，但我不能：

isDeterministic[au_] := Module[{a, s},
  For[i = 1, i <= Length[au[[3]]],
   a = au[[3]][[i]][[1]];
   s = au[[3]][[i]][[2]];
   If[s == {}, Return[False]];
   For[j = i, j <= Length[au[[3]]],
    If[a == au[[3]][[j]][[1]] && s == au[[3]][[j]][[2]], 
     Return[False]];
    j++;
    ];
   i++;
   ];
  Return[True];
  ]
A = {{1, 2},
  {a, b},
  {{1, a, 2}, {2, b, 1}},
  1,
  {2}
  }
isDeterministic[A]

A 是一个自动机，其中第一个元素是状态列表，第二个是字母表，第三个是转换，第四个是初始状态，第五个是最终状态列表。

主要问题是，当我将函数应用于 A 时，它永远不会结束。

编辑：已解决

这是最终代码：

isDeterministic[au_] := 
 Module[{a, s, lambda}, 
  For[i = 1, i <= Length[au[[3]]], i++, a = au[[3]][[i]][[1]];
   s = au[[3]][[i]][[2]];
   If[s == lambda, Return[False]];
   For[j = i + 1, j <= Length[au[[3]]], j++, 
    If[a == au[[3]][[j]][[1]] && s == au[[3]][[j]][[2]], 
     Return[False]]]];
  True]

A = {{1, 2},
  {a, b},
  {{2, b, 1}, {1, a, 2}},
  1,
  {2}
  }

isDeterministic[A]

True
4

2 回答 2

1

我讨厌看到人们在 Mathematica 中编写循环，它们几乎总是不必要的，而且几乎在所有情况下都有更好的选择，更好的是执行速度更快，更容易编写和理解。这种易于编写和理解的部分仅来自于按照 Mathematica 设计使用的方式做事的经验，但如果您继续以命令式风格进行编程，您将永远无法获得。

好的，讲道就够了，上一些 Mathematica。我将从定义一个不确定的自动机开始

aub = {{1, 2, 3}, {a, b}, {{1, a, 2}, {2, b, 1}, {2, b, 3}}, 1, {2}};

将规则的第一个子句用于确定自动机的确定性，首先将转换集按其前 2 个元素分组。表达方式

GatherBy[aub[[3]], {First[#], First[Rest[#]]} &]

产生输出

{{{1, a, 2}}, {{2, b, 1}, {2, b, 3}}}

如果您仔细检查，您会发现这是一个列表列表，每个列表都是前 2 个元素（开始状态和事件）匹配的转换列表。现在检查这些列表的长度很简单：

Map[Length[#] == 1 &, GatherBy[aub[[3]], {First[#], First[Rest[#]]} &]]

生成列表

{True, False}

最后，将最后一个表达式的头部更改为And，我们得到

And @@ Map[Length[#] == 1 &, GatherBy[aub[[3]], {First[#], First[Rest[#]]} &]]

这给出了响应

False

接下来，确定确定性规则的第二个子句要求没有空转换。我不确定您将如何建模这些，我假设这样的转换看起来像{1,{},2}一个带有空事件列表的开始和结束状态。我需要另一个测试用例

auc = {{1, 2}, {a, b}, {{1, a, 2}, {2, {}, 1}, {2, b, 1}}, 1, {2}};

要检查这一点，首先从转换中获取所有事件的集合：

auc[[3, ;; , 2]]

返回

{a, {}, b}

我已经使用;;符号对转换数组进行切片并仅从中选择事件。然后

FreeQ[auc[[3, ;; , 2]], {}]

检查空列表是否在转换的切片中。当然，在这种情况下，表达式返回False。

所以，我建议这个功能

isDeterministic[au_]:=And[(And @@ 
   Map[Length[#] == 1 &, 
    GatherBy[au[[3]], {First[#], First[Rest[#]]} &]]), 
 FreeQ[au[[3, ;; , 2]], {}]]

替换您的基于循环的方法。

或者随意忽略这个无端的建议。

于 2012-11-14T06:36:04.253 回答
1

尝试这个

isDeterministic[au_]:=Module[{a,s,len = Length[au[[3]]] },

  For[i = 1, i <= len, i++,

     a=au[[3]][[i]][[1]];
     s=au[[3]][[i]][[2]];

     If[s=={}, Return[False,Module] ];

     For[j = i, j <= len, j++,

        If[a==au[[3]][[j]][[1]]&&s==au[[3]][[j]][[2]],
           Return[False,Module]
        ]
     ]
  ];

  True
 ]
于 2012-11-14T00:57:31.853 回答