1

私はアルファベットの上に次の言語を持っています{1,0}L= {w | wのすべてのプレフィックスには、0よりも1が多くありません}

L（M）= L（G）となるようにGからNPDA Mを構築するにはどうすればよいですか？またはその変換を行うために、任意のWebページを推奨できますか？

4

1 に答える 1

0

一般に、言語のNPDAを作成する方法は、CFGとNPDAの間のマッピングがかなり単純であるため、文法を見つけることだけです。

そのような言語のCFG（文脈自由文法）は次のようになります

S -> S "0" S | "" | S "0" S "1" S | S "1" S "0" S

文脈自由文法ができたら、そのNPDAの構築は比較的簡単なはずです;）

ところで、あなたは上記の投稿でGとは何かについて言及していないので、記述された言語のNPDAを構築する方法の説明が必要だと思いました。他に何か意味がある場合は、教えてください。説明を更新します。

于 2011-05-11T06:39:39.473 に答える