Эта грамматика встречалась в разделе 00 (где выводимость в ней проверялась с помощью стека).

Пример 2. Другая грамматика, порождающая тот же язык:

Алфавит: ( ) [ ] T E

Правила:

E ->

E -> TE

T -> (E)

T -> [E]

Начальным символом во всех приводимых далее примерах будем считать символ, стоящий в левой части первого правила (в данном случае это символ T), не оговаривая этого особо.

Для каждого нетерминального символа можно рассмотреть множество всех слов из терминальных символов, которые из него выводятся (аналогично тому, как это сделано для начального символа в определении выводимости в грамматике). Каждое правило грамматики можно рассматривать как свойство этих множеств. Покажем это на примере только что приведенной грамматики. Пусть SetT и SetE —множества слов (из скобок), выводимых из нетерминалов T и E соответственно. Тогда правилам грамматики соответствуют такие свойства:

E -> SetE содержит пустое слово

E -> TE если слово A принадлежит SetT,

Слово B принадлежит

SetE, то слово AB принадлежит SetE

T -> [E] если A принадлежит

SetE, то слово [A] принадлежит SetT

T -> (E) если A принадлежит

SetE, то слово (A) принадлежит SetT

Сформулированные свойства множеств SetE, SetT не определяют эти множества однозначно (например, они остаются верными, если в качестве SetE и SetT взять множество всех слов). Однако можно доказать, что множества, задаваемые грамматикой, являются минимальными среди удовлетворяющих этим условиям.