Context free Language および Deterministic Context free languages で決定できる、認識している問題を挙げていただけますか。Stack Overflow と Wiki で決定不能な問題のリストに関する情報を入手しましたが、CFG や DCFG とは詳細には関係ありません。この問題のリスト (証明/リンク付き) は、そのような問題を探している人にとって非常に役立つ可能性があります。
質問する
651 次
1 に答える
0
DCFG と CFG に関連する非常に興味深い決定可能問題の 1 つがそれです。2 つの DCFG (DPDA) を比較できますが、2 つの CFG を比較することはできません。DPDA(DCFG)の等価問題は決定可能であることが証明されています。[リンク] ( http://www.lfcs.inf.ed.ac.uk/reports/99/ECS-LFCS-99-411/ECS-LFCS-99-411.pdf ) このドキュメントで非常によく説明されています。
于 2014-02-25T12:21:06.117 に答える