Контекстно-свободные грамматики

Свойства контекстно-свободных (КС) грамматик.

1) Дают возможность изучения структур синтаксических деревьев вывода.

2) Обладают способностью порождать бесконечные языки.

F Определение: 1) Цепочку h будем называть подцепочкой цепочки x, если последняя может быть представлена в виде x = x ₁ h x ₂. Здесь x ₁ и x ₂ – некоторые (возможно, пустые) цепочки.

2) Вхождением подцепочки h в цепочку x будем называть пару объектов (h, i), где h – данная подцепочка, а i – порядковый номер левого символа подцепочки h в цепочке x.

Пример 9: Цепочка acac включает в себя две подцепочки ac. Таким образом, можно рассматривать два возможных вхождения подцепочки ac: (ac,1) и (ac,3).