Порождающая грамматика

Существуют разные способы задания языков. Если язык конечен, то его в принципе можно задать перечислением всех принадлежащих ему цепочек. Для бесконечного языка такой способ невозможен, в этом случае язык задается некоторой грамматикой. Порождающая грамматика G, задающая язык L, определяется как четверка множеств:

G(L) = {Σ, N, S, P},

где Σ – алфавит (множество) символов языка; N – алфавит (множество) символов грамматики; S – подмножество символов грамматики, называемых начальными, ; P – множество порождающих правил вида:

α → β,

где α и β – цепочки символов из алфавитов языка Σ и грамматики N, причем в цепочке α должно быть не менее одного символа из алфавита N. Каждое из правил задает подстановку, т.е. замену цепочки α на цепочку β.

Цепочку α называют левой, а цепочку β – правой частью порождающего правила. Если выполняется неравенство |α| ≤ |β|, то такое порождающее правило называют неукорачивающим. Если же |α| > |β|, то порождающее правило называется укорачивающим. В общем случае допустимо, чтобы в некоторых правилах цепочка β была пустой.

Далее в примерах заглавными латинскими буквами будут обозначаться символы грамматики (из алфавита N), строчными буквами и другими знаками – символы языка (из алфавита Σ), строчными греческими – цепочки символов (из обоих алфавитов N и Σ).

Дата добавления: 2015-07-26; просмотров: 172; Нарушение авторских прав

Мы поможем в написании ваших работ!