2010-11-26 10 views
2

私の目標は、OCamlに入力を取り込む遷移関数を実装することです。文字は正の論理式(真と偽を含む)を返します。ある :\デルタ(Q0、A)= Q1および(Q2またはQ3)オートマトンの遷移関数

私の問題は、OCamlのブール式を表現する方法と有限オートマトンを交互この特定

答えて

2

有する遷移関数を実装する方法であります、え?ブール式を表現する

は(私はまだ状態のタイプを指定したくないので、ポリモーフィック型にするつもりだという)単純な再帰バリアント型で行うことになります。

type ’state formula = 
    | And  of ’state formula list 
    | Or  of ’state formula list 
    | Literal of bool 
    | Variable of ’state 

ので、例えば、q1 and (q2 or q3)のように表されます:あなたはどちらか、実際のOCamlの関数としての機能を表すことができる

And [ Variable q1 ; Or [ Variable q2 ; Variable q3 ] ] 

type state = Q0 | Q1 | Q2 | Q3 
let delta : state * char -> state formula = function 
    | Q0, 'a' -> And [ Variable Q1 ; Or [ Variable Q2 ; Variable Q3 ] ] 
    | _ -> ... 

それとも、マップ内の遷移を格納するために選ぶことができます(これは、実行時に、あなたのオートマトンを構築することができます):

type state = int 

module OrderedStateChar = struct 
    type = state * char 
    let compare = compare 
end 

module StateCharMap = Map.Make(OrderedStateChar) 

let transition_of_map map = 
    fun (state,char) -> 
    try StateCharMap.find (state,char) map 
    with Not_found -> Literal false 

let map = List.fold_left 
    (fun map (state,char,formula) -> StateCharMap.add (state,char) formula map) 
    StateCharMap.empty 
    [ 
    0, 'a', And [ Variable 1 ; Or [ Variable 2 ; Variable 3 ] ] ; 
    ... 
    ] 

let transition = transition_of_map map 

let _ = transition (0,'a') (*/* returns '1 and (2 or 3)' */*) 
+0

はいが交互有限オートマトン、返信用のおかげで、最後の事である:あなたの場合どのように私はできるの状態の数を知らないのですか? – kafka

+0

2番目のソリューションを使用して、すべてのステートに数値を与えます(ステートは整数としてエンコードされるため、ステート数は任意です)。 –

+0

あなたの答えはもう一度ありがとう – kafka