Методы искусственного интеллекта для машинного перевода текстов. Роганов В.Р - 11 стр.

       Элементы множества V — Σ называются вспомогательными символами
(или переменными).
       Элементы множества Σ называются основными символами (или буквами).
Σ и V — Σ называются соответственно основным и вспомогательным алфави-
том.
       Элементы (u, v) множества P называются правилами (или правилами под-
становки) и записываются обычно в виде u → v.
       Элемент σ называется начальным символом или аксиомой.
       Содержательно элементы множества V — Σ представляют собой «мета-
лингвистические переменные» или «синтетические классы» (иначе «граммати-
ческие классы»).
       Элементы множества Σ — элементарные единицы определяемого языка.
       P — множество грамматических правил.
       σ — синтаксический класс «предложений».
       Укажем теперь, как применяются правила. Способ их применения есть
обобщение процедуры замены, проиллюстрированной на рисунке.
       Определение. Пусть G = (V, Σ, P, σ) — порождающая грамматика и w, y ∈
V*. Будем писать w ⇒ y (или w ⇒ y, если G подразумевается), если существуют
z1, z2, u и v, такие, что w = z1uz2, y = z1vz2 и u → v ∈ P. Далее, пишем w ⇒* y (или
w ⇒* y, если G подразумевается), если либо w = y, либо существуют w0, ..., wr,
такие, что w0= w, wr = y и wi ⇒ wi+1 для всех i. Последовательность w0, ..., wr на-
зывается выводом (длины r) и записывается в виде
                                  w0 ⇒ w1 ⇒ ... ⇒ wr.
       Иначе: ω ⇒∗ ψ реализуется с помощью вывода ω0 ⇒ ω1 ⇒ ... ⇒ ωρ. Бу-
дем говорить также, что ω0 ⇒ ω1 ⇒ ... ⇒ ωρ есть вывод wr из w0.
       Используя введенные только что понятия, мы можем указать способ, при
помощи которого грамматика выделяет цепочки, составляющие «язык».
       Определение. Пусть G = (V, Σ, Π, σ) — порождающая грамматика. Мно-
жество L(G) = {x ∈ Σ∗⏐σ ⇒∗ x} называется языком, порождаемым граммати-

                                                                                 11