6

私は、コンパイラでnfaまたはdfaを使用する方が適切であり、どのような状況であるかについての議論を探しています。nfaとdfaをシミュレートすることの時間計算量のトレードオフは何ですか？また、コンパイラーのどのような状況でどちらがより適切ですか？

4

1 に答える 1

3
  • NFAからのDFAの構築時間はO（2 ^ m）です。ここで、mはノードの数です。
  • DFAの実行時間はO（n）です。ここで、nは入力文字列の長さです。これは、特定の文字列に対してDFAを通過するパスが1つしかないためです。
  • NFAの構築時間はO（m）である必要があります。ここで、mはノードの数です。
  • NFAの実行時間はO（m²n）です。これは、非決定性であり、コンピューターが文字列内の現在の文字のすべての可能なパスをチェックする必要があるためです。（先読みがないと仮定すると、次のキャラクターがどうなるかわからないため、行き止まりになります）

これらの数字は、UAに簡単なアイデアを与えるかもしれません

于 2015-08-31T09:39:57.140 に答える