2

オートマトンが決定論的であるかどうかを返すモジュールを数学で作りたい。同じ状態で始まり、同じシンボルを読み取る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はオートマトンで、最初の要素は状態のリスト、2番目はアルファベット、3番目は遷移、4番目は初期状態、5番目は最終状態のリストです。

主な問題は、関数を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

これを試して

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 に答える
1

Mathematicaでループを書いている人を見るのは嫌いです。ほとんどの場合、ループは不要です。ほとんどの場合、実行が速く、書き込みと理解の両方が簡単であるという意味で、より優れた代替手段があります。この書きやすさと理解のしやすさのいくつかは、Mathematicaが使用されるように設計された方法で物事を行う経験を伴うだけですが、命令型でプログラミングし続けると、それは決して得られません。

OK、十分に敬意を表して、いくつかの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

次に、決定論を決定するためのルールの2番目の節では、空の遷移がないことが必要です。これらをどのようにモデル化するかはわかりません。このような遷移は{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 に答える