Пример построения непосредственных выводов на примере грамматики натурального числа

С помощью непосредственных выводов можно получать цепочки, состоящие только из терминальных символов.

2. Вывод цепочки w из цепочки v.

Говорят, что цепочка v порождает цепочку w (w выводится из v), если существует следующая последовательность непосредственных выводов

Если v≠w, то (непосредственная выводимость)

Если v=w или , то вводят следующее обозначение

Общее правило вывода

Для вывода w из v необходимо последовательно менять нетерминальные символы в v на правые части соответствующих правил из грамматики.

Из предыдущего примера следует, что

3. Пусть G(z) - грамматика. Цепочка x называется сентенциональной формой, если она выводится из начального символа, то есть

4. Предложение языка – это сентенциональная форма, состоящая только из терминальных символов.

5. Язык – это множество предложений, то есть цепочек, выводимых из начального символа <z> и состоящих из терминальных символов.

,

где Т⁺ - усеченная итерация множества терминальных символов

2. Пример построения логического плана выполнения запроса к базе данных.

Пример построения логического плана