Однозначная контекстно-бесплатная грамматика

Question

Я читал контекстную грамматику и столкнулся с неоднозначной грамматикой. Если язык, созданный CFG, имеет более 1 дерева разбора, то CFG является неоднозначной грамматикой. Есть ли способ, которым я могу узнать или доказать, что грамматика однозначна. В общем, я могу протестировать некоторый язык, созданный CFG, и проверить, генерируется ли более одного дерева разбора на этом языке, чтобы показать, что грамматика неоднозначна. Но как мне проверить или доказать, что давать CFG однозначно?

Answer 1

Проблема неоднозначности для CFG неразрешима в общем случае. Однако есть несколько способов проверить, может ли язык быть неоднозначным. Проверьте эту статью, если вы хотите, чтобы теория этого; для чего-то более практичного, рассмотрите это или это.