ПОРАЖДЕНИЕ ЯЗЫКОВ ГРАММАТИКАМИ.


Формальные языки классифицируются по типу грамматики, которая их порождает, то есть язык, порожденный грамматикой типа 0, называется языком типа 0. Язык, порожденный грамматикой типа 1, называется языком типа 1. Язык, порожденный грамматикой типа 2, называется языком типа 2. Язык, порожденный грамматикой типа 3, называется языком типа 3.

ТЕМА 1.4. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ (КС ГРАММАТИКИ).

По определению КС грамматики могут быть как укорачивающими, так и неукорачивающими. У укорачивающих КС грамматик множество продукций содержит продукции вида . Очевидно, что никакая другая продукция не может привести к уменьшению длины строки при выводе.
Наличие у КС грамматики продукций вида осложняет процедуру грамматического разбора и выводов в КС грамматике.
Продукцию вида будем называть е-ПРОДУКЦИЕЙ, а грамматику, которая не имеет такой продукции е-СВОБОДНОЙ (НЕУКОРАЧИВАЮЩЕЙ).