Понимание основ CFG

Question

Вы только что начали главу о КЛЛ в книге Сипсера и уже не понимаете основ.

Пусть это будет грамматика некоторого языка:

S -> A0A 
A -> 00A | 11A | 10A | 01A | e

Я действительно запутался в этой части A0A. Означает ли это, что левая сторона от 0 должна быть всегда такой же, как правая? Значит ли это, что 00011 или 000 не на этом языке?

Answer 1

Любой S любой вариант у вас есть для любого Aсопровождаемый единственным литералом 0 а потом еще один вариант для A, каждый A является независимым

Строка 00011 на языке, потому что вы можете выбрать два As (например) так, что первый 00A а второй 11A, Если вы выберете рекурсивно пустую строку (e) для обоих "оставшихся" As, когда вы объединяете все, вы получите строку 00011,

Вы можете сделать то же самое, чтобы получить строку 000,

Answer 2

A преобразуется либо в пустую, либо в две двоичные цифры, чем A. Это означает, что A преобразуется в любую последовательность четного числа двоичных цифр.

S преобразуется в A, затем в 0, затем в A. Это означает, что S преобразуется в четное число двоичных цифр, затем в 0, затем в четное число двоичных цифр. То есть S - любая последовательность нечетного числа двоичных цифр с 0 в середине.

Означает ли это, что левая сторона от 0 должна быть всегда такой же, как правая?

Нет почему? Два разных А могут преобразовываться в разные последовательности.