Разработка компиляторов
Эквивалентность грамматик
Две грамматики назовем эквивалентными, если совпадают порождаемые ими языки. Грамматика, приведенная на данной иллюстрации, эквивалентна грамматике, приведенной на предыдущей.
Можно увидеть, что эта грамматика получена из предыдущей с помощью устранения цепных правил. Как и в случае обычных грамматик, любая деревянная грамматика может быть приведена к эквивалентной, не содержащей цепных правил.
Проблема определения эквивалентности грамматик разрешима, хотя для неоднозначных грамматик (определение неоднозначных грамматик будет дано ниже) это может потребовать экспоненциального времени.
