Unamiguous Context free Grammar

Question

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

Answer 1

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