computer-science - 非決定論的な有限トランスデューサをどのようにシミュレートできますか?

Question

非決定性オートマトンは、オートマトンの状態と入力文字列のどこまで到達したかを追跡するだけで、入力文字列で簡単にシミュレートできます。しかし、非決定論的なトランスデューサ (もちろん、トランスデューサは入力シンボルを出力シンボルに変換し、ブール値だけでなく文字列を出力として与えることができます) をどのようにシミュレートできますか? 非決定性のために多数になる可能性がある出力文字列を何らかの方法で追跡する必要があるため、これはより複雑なようです。

Answer 1

基本的には NFA の場合と同じことを行いますが、今回は true または false を返す代わりに、出力を出力セットに追加します。ここにちょっとした疑似コードがあります:

function rec(in, current_state, pos, out)
 if(current_state.isFinal && pos == in.length) out_set += out

 for(t <- lambda transition going out from current_state)
  rec(in, t.destination, pos, out + t.output_symbol)

 for(t <- transition going out from current_state for symbol in(pos)
  rec(in, t.destination, pos+1, out + t.output_symbol)