數學確定自動機

我想在mathematica中創建一個模塊，該模塊在自動機是確定性或非確定性時返回。我在考慮如果有兩個轉換開始於相同的狀態並讀取相同的符號或者如果存在空的轉換，則自動機不是確定性的。數學確定自動機

欲調試代碼，但我不能：

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

來源

2012-11-14 user1754322

試試這個

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-14 00:57:31 Nasser

感謝您的回答！現在沒有無限循環，但它顯示False時，它應該顯示爲真 – user1754322

好吧，非常感謝你的民間。最後，我解決了邏輯部分只是添加1到j。我將編輯以顯示最終代碼。 Module中的大寫字母是我難以發現的一個錯誤。 – user1754322

我討厭看到人在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[#]]} &]]

wh ICH給出了迴應

False

下一頁您的規則來確定決定的第二條要求有沒有空的轉變。我不確定你將如何對這些模型進行建模，我會假設這種轉換看起來像{1,{},2}，這是一個開始和結束狀態，帶有一個空的事件列表。我需要另一個test case

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

要檢查這一點，首先從轉變得到了集中的所有事件：

auc[[3, ;; , 2]]

回報

{a, {}, b}

我用;;表示法來切片e轉換數組並僅從中選擇事件。然後

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

檢查空單是否在轉變的切片。當然在這種情況下，表達式返回False。

所以，我建議功能

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

取代你的循環爲基礎的方法。

或隨意忽略這種無償的建議。

來源

2012-11-14 06:36:04

酷！我喜歡。我使用For，因爲我習慣用C/C++，Java和ASM編程。我很難改變主意。無論如何，我會從你的代碼中學到很多東西。謝謝！ – user1754322

數學確定自動機

回答

相關問題