Лекция № 6

1.4. Технология формирования предложений языка

1.4.1. Выводимость цепочек

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Чтобы дать формальное определение процессу вывода введем несколько дополнительных понятий.

Во-первых, цепочка  = ₁₂ называется непосредственно выводимой из цепочки  = ₁₂ в грамматике G<T, N, P, S>, V = T  N, ₁, , ₂  V^*,   V⁺, если в грамматике G существует правило: (  )  P. Непосредственная выводимость  из  обозначается так:   . Выводимая цепочка стоит в правой части вывода. При этом выполняется подстановка подцепочки  вместо подцепочки . Иными словами цепочка  непосредственно выводима из цепочки  в том случае, если можно взять несколько символов в цепочке , заменить их на другие символы согласно некоторому правилу грамматики и получить цепочку .

В формальном определении непосредственной выводимости любая из цепочек ₁ ₂ или обе эти цепочки могут быть пустыми. В предельном случае вся цепочка  может быть заменена на цепочку , если в G существует правило: (  )  P.

Второе дополнительное понятие – понятие выводимой цепочки. Цепочка  называется выводимой из цепочки  ( ^* ) в том случае, если выполняется одно из двух условий:

–  непосредственно выводима из  ();

– существует такая цепочка , что , выводимая из  ( ^* ) и  непосредственно выводима из  (  ).

Это рекурсивное определение выводимости цепочки. Суть его заключается в том, что цепочка  выводима из цепочки  либо непосредственно, либо через построение последовательности непосредственно выводимых цепочек от  к  следующего вида:

  ₁  …  _I  …  _n  , n  1.

Такая последовательность непосредственно выводимых цепочек называется цепочкой вывода или выводом. Каждый переход от одной непосредственно выводимой цепочки к следующей в цепочке вывода называется шагом вывода. Если число промежуточных цепочек n, то число интервалов n + 1.Если число шагов равно 1, т. е. n = 0, то () ( непосредственно выводима из ).

Если n  1, т. е. число шагов вывода два или более, то цепочка вывода имеет специальное обозначение:  ⁺ . При этом говорят, что цепочка  нетривиально выводима из цепочки . Если количество шагов вывода известно, то его можно указать вместо знака +. Например, запись  ⁴  означает, что цепочка  выводится из цепочки  за 4 шага. Если цепочка  и  равны ( = ), то может быть такое обозначение цепочки вывода  ⁰ .

Возьмем грамматику G из 1.3.1, набор правил которой P:

S  T+ T– T

T  FTF

F  0123456789.

Построим в ней несколько произвольных выводов.

1. S  – T  – TF  – TFF  – FFF  – 4FF  – 47F  – 479.

2. S  T  TF  T8  F8  18.

3. T  TF  T0  TF0  T50  F50  350.

4. TFT  TFFT  TFFF  FFFF  1FFF  1FF4  10F4  1004.

5. F  5.

В результате получаются следующие выводы.

1. S ^* – 479 или S ⁺ – 479 или S ⁷ – 479.

2. S ^* 18 или S ⁺ 18 или S ⁵ 18.

3. T ^* 350 или T ⁺ 350 или T ⁶ 350.

4. TFT ^* 1004 или TFT ⁺ 1004 или TFT ⁷ 1004.

5. F ^* 5 или F ¹ 5 (утверждение F ⁺ 5 неверно!).

Вопрос слушателям. Почему утверждение F ⁺ 5 неверно?

Все эти выводы построены на основе грамматики G. В примере в этой грамматике можно построить сколь угодно много цепочек вывода.