Эквивалентность грамматик

Определение Грамматики G ₁ и G ₂ называются эквивалентными, если они определяют один и тот же язык, т.е. .

Определение Грамматики G ₁ и G ₂ называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов т.е. .

Пример Для грамматики G ₁ эквивалентной будет грамматика G ₂ = ({0, 1}, { S }, P ₂, S), где множество правил вывода P ₂ содержит правила вида S ® 0 S 1| e.

Почти эквивалентной для грамматики G ₁ будет грамматика G ₃ = ({0, 1}, { S }, P ₃, S), где множество правил вывода P ₃ содержит правила вида S ® 0 S 1|01.