Этот контекст грамматики свободен или нет?

Question

G:    S ---> aSb
      S ---> λ

Как мне показалось, первое производственное правило не зависит от контекста (потому что левая сторона меньше правой стороны), но для второго производственного правила это не так (потому что длина левой стороны равна правой стороне).

Ну, что мы можем сказать по этой грамматике в этом утверждении. Это не зависит от контекста или нет?

Answer 1

Это не зависит от контекста.

"Свободный от контекста" относится к наличию контекста в левой части производственного правила.
Неважно, что правая сторона одинаково длинна; имеет значение только то, что левая сторона состоит из одного нетерминала.
Когда левая часть производственного правила состоит из одного нетерминала, правило может применяться везде, где появляется этот нетерминал, независимо от контекста, в котором оно появляется.

Если бы правило было, например, aS ---> λтогда это будет контекстно-зависимым; он может применяться только в тех местах, где нетерминал S предшествовал конечный символ a; когда это было в контексте предшествующего a,

Для полноты грамматика не зависит от контекста, если все ее производственные правила таковы.