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

кой. (Иначе — грамматика G порождает язык L(G).) Каждая цепочка языка
L(G) является выводимой из σ.
           Итак, для каждой порождающей грамматики G порождаемый ею язык
есть множество L(G) = Σ∗ ∩ DG, где DG — наименьшее множество, которое
           1) содержит σ,
           2) содержит цепочку uyv всякий раз, когда uyv∈ DG и w → y ∈ P.
           Другими словами, порождающая грамматика выделяет именно те цепоч-
ки из множества Σ*, которые являются выводимыми из σ.
           Произвольные порождающие грамматики могут порождать множества
общего вида. Поэтому мы наложим на допустимые правила подстановки два
ограничения. Каждое из этих ограничений приводит к возникновению некото-
рого специального семейства формальных языков.
           Определение. Порождающая грамматика G = (V, Σ, P, σ) называется
грамматикой непосредственно составляющих (НС–грамматикой), если каж-
дое ее правило имеет вид uξv → uyv, где ξ ∈ V — Σ; u, v∈ (V — Σ)* и
y ∈ V* — {ε}. Язык, порождаемый НС–грамматикой, называется НС–языком.
           Таким образом, замена символа ξ цепочкой y возможна лишь в контексте
u ... v.
           Существуют языки L ⊆ Σ∗ — {ε}, порождаемые грамматиками и не яв-
ляющиеся НС–языками. Несмотря на несомненную важность НС–языков для
изучения естественных языков и языков программирования, о них известно не-
много и мы не будем ими заниматься.
           Определение. Порождающая грамматика G = (V, Σ, Π, σ) называется кон-
текстно-свободной (КС–грамматикой), если каждое ее правило имеет вид
ξ → v, где ξ ∈ V — Σ и v∈ V*. Язык L ⊆ Σ∗ называется контекстно-свободным
языком (КС–языком), если он порождается КС–грамматикой.
           Термин «контекстно-свободная» в названии грамматики отражает тот
факт, что замена вспомогательного символа на цепочку не зависит от контек-
ста.

                                                                             12