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

При реализации в АСИЗ блоков анализа протоколов часто приходится решать задачу построения (восстановления) формальной грамматики по известному множеству, порожденных ею предложений. В литературе [47] эта задача известна как задача грамматического вывода. Для того, чтобы получить в свое распоряжение конструктивные, математически обоснованные методы восстановления грамматик, прежде всего необходимо привести формальную постановку задачи грамматического вывода.

В настоящей главе предлагаются методы восстановления, состоящие из двух стандартных этапов. Причем подзадачи, решаемые на каждом из этих этапов, относительно независимы друг от друга.

4.1 Постановка задачи грамматического вывода

Для удобства последующего изложения, следуя [4], приведем основные понятия теории формальных грамматик и примем ряд связанных с ними стандартных обозначений.

Алфавитом называется любое конечное множество символов. Конечная последовательность символов a₁a₂...a_k, где a_i ∈ Σ Σ, (i=1,2,...,k), называется цепочкой в алфавите Σ. Длина последовательности называется длиной цепочки; длину цепочки x будем обозначать |x|.

Пустой называется цепочка длины 0. Пустую цепочку будем обозначать символом e (|e| = 0).

Пусть x - цепочка в некотором алфавите. Для любого целого i (i ≥ 0) определим цепочку xⁱ следующим образом:

Обозначим Σ^* - множество всех цепочек в алфавите Σ, включая пустую цепочку, а Σ⁺ = Σ^* \ {e}.

Контекстно-свободной грамматикой (КС-грамматикой) называется четверка G = < N, Σ, P, S >, где
N - алфавит нетерминальных символов (нетерминалов);
Σ - непересекающийся с N алфавит терминальных символов (терминалов);
P - конечное множество правил вывода вида A → α, где A ∈ N, α ∈ (N ∪ Σ)^*;
S - выделенный символ из N, называемый начальным символом.

Примем следующие соглашения относительно обозначений символов и цепочек, связанных с грамматиками:
(а) a, b, c, ... и цифры 0, 1, 2, ... обозначают терминалы;
(б) A, B, C, ... - обозначают нетерминалы;    S - начальный символ;
(в) X, Y, Z - обозначают либо терминалы, либо нетерминалы;
(г) α, β, γ - обозначают цепочки, которые могут содержать как терминалы, так и нетерминалы;
(д) u, v, w, x, y, z - обозначают цепочки, состоящие только из терминалов.

С учетом принятых соглашений грамматику можно задавать множеством правил вывода.

Пусть G = < N, Σ, P, S > - КС-грамматика. Правила из P, у которых левая часть есть нетерминал A, называются A-правилами. Множество всех правых частей A-правил из P обозначим R(G,A),

Пусть G = < N, Σ, P, S > - КС-грамматика. На множестве цепочек (N ∪ Σ)^* определим бинарное отношение непосредственной выводимости =>_G следующим образом: α =>_G β тогда и только тогда, когда

Цепочка α называется выводимой в грамматике G, если S =>^*_G α. Каждому выводу цепочки α однозначно соответствует дерево вывода.

Язык, порождаемый грамматикой G (обозначается L(G)), есть множество терминальных цепочек

Две грамматики называются эквивалентными, если порождаемые ими языки совпадают.

Вывод цепочки α в грамматике G = < N, Σ, P, S >

КС-грамматика G называется однозначной, если для каждого предложения из L(G) существует единственный левый вывод.

КС-грамматика называется праволинейной, если все ее правила вывода имеют вид A → xB или A → x, где A и B - нетерминалы, x ∈ Σ^*.

Задача грамматического вывода рассматривается в связи с функционированием некоторой абстрактной системы, состоящей из источника и анализатора.

Источник - это некоторое устройство, которое располагает языком L_и (языком источника). На каждом такте своей работы источник передает одно новое слово из L_и на вход анализатора. Фактически источник формирует (вообще говоря - бесконечную) последовательность множеств {Ω_i | i ≥ 1}, где Ω_i состоит из предложений, переданных на первом, втором, ..., i-м тактах. Каждое множество Ω_i называется образцом.

Анализатор - это устройство, которое на i-м такте своей работы по образцу Ω_i строит конечное множество грамматик G_i (множество решающих грамматик). При этом анализатор применяет к образцу алгоритм (метод) восстановления M.

Определение.
Задача грамматического вывода называется разрешимой для языка источника L_и, последовательности образцов {Ω_i | i ≥ 1} и метода восстановления M, если существует число n, при котором множество решающих грамматик G_n, полученное из образца Ω_n методом М, содержит грамматику G_и такую, что L(G_и) = L_и.

В дальнейшем будем рассматривать только бесконечные языки источника, поскольку для конечных языков сформулированная задача грамматического вывода решается тривиально.

Определение.
Последовательность образцов {Ω_i | i ≥ 1} называется полной положительной, если для любого j ≥ 1 существует m = m(j,L_и) такое, что { x ∈ L_и   |   |x| ≤ j } ⊂ Ω_m.

Основу задачи грамматического вывода составляет метод построения множества решающих грамматик по известному образцу Ω = Ω_i. Переходя к описанию методов восстановления, отметим, что практически все они представляют собой комбинацию двух самостоятельных процедур: метода структурирования и метода обобщения. Метод структурирования по известному образцу Ω строит конечную структуру, порождающую элементы Ω. Метод обобщения преобразует структуру образца таким образом, чтобы она порождала и некоторые другие предложения.

Ориентируясь на свойства последовательности образцов, методы восстановления грамматик разрабатываются в расчете на некоторый класс языков источника. В этом смысле можно говорить о задаче восстановления языков заданного типа. Ниже рассматриваются методы восстановления контекстно-свободных языков.

4.2 Структура контекстно-свободных языков

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

Каждый КС-язык порождается некоторой КС-грамматикой. В интересах задачи восстановления данное утверждение предстоит усилить и показать, что класс грамматик, порождающих КС-языки, можно ограничить так называемыми нормальными грамматиками. В настоящем изложении нормальные грамматики используются для определения структуры КС-языков. Однако самое существенное свойство нормальных грамматик состоит в том, что они определяют класс структур взаимно однозначным образом.

4.2.1 Нормальные контекстно-свободные грамматики

Выделим некоторые характеристики КС-грамматик, которые в дальнейшем будем рассматривать как дефекты, подлежащие устранению.

Определение [4]
Пусть G = < N, Σ, P, S > - КС-грамматика.
Правило вывода вида A → e называется e-правилом.
Правило вывода вида A → B называется цепным правилом.
Правило A → α называется бесполезным, если в грамматике G не существует вывода вида

S =>^*_G xAz =>_G xαz =>^*_G xyz

Определение.
Нетерминал A КС-грамматики G называется простым, если ||R(G,A)|| = 1.

Перейдем к определению еще одного свойства КС-грамматик. Будем рассматривать разбиения K множества нетерминалов КС-грамматики G = < N, Σ, P, S >. K = { K_C | C ∈ N'}. (Здесь в качестве индексов используются символы некоторого алфавита N'.) Каждое разбиение K порождает

Определение 4.1
Разбиение нетерминалов КС-грамматики G = < N, Σ, P, S > называется согласованным, если для любых нетерминалов A и B равенство h_K(A) = h_K(B) имеет место тогда и только тогда, когда для любого A-правила

h_K(A₁) = h_K(B₁),   ...,   h_K(A_n) = h_K(B_n).

Лемма 4.2
Если K - согласованное разбиение множества нетерминалов КС-грамматики G, то L(G) = L(G_K).

Доказательство. Зафиксируем некоторое согласованное разбиение K произвольной КС-грамматики G = < N, Σ, P, S >. Для сокращения записи введем более компактные обозначения: h = h_K, H = H_K, G' = G_K = < N',Σ,P',C' >.

Рассмотрим произвольное предложение x из L(G) и некоторый левый вывод x в грамматике G.

Покажем, что последовательность цепочек H(α₀), ..., H(α_k) есть левый вывод предложения x в грамматике G'.

По определению левого вывода α₀ = S и H(α₀) = C', то есть H(α₀) - цепочка, выводимая в грамматике G_K.

Предположим, что цепочка H(α_i) выводима в грамматике G' для некоторого i < k. По определению левого вывода для грамматики G цепочки α_i и α_i+1 можно представить в виде

По определению грамматики G' имеем

Рассмотрим произвольное предложение y из L(G') и некоторый левый вывод y в грамматике G'.

Положим α₀ = S, при этом h(S) = C'.

Предположим, что удалось построить вывод

Как следует из определения левого вывода, в грамматике G' существует правило

Следствие.
Если G - праволинейная грамматика, то G_K - также праволинейная грамматика.
Если G - однозначная КС-грамматика, то G_K - также однозначная КС-грамматика.

Определение.
КС-грамматика G = < N, Σ, P, S > называется избыточной, если существует согласованное разбиение нетерминалов K такое, что ||K|| < ||N||.

Проверка грамматики G на избыточность сводится к перебору и оценке на согласованность всевозможных разбиений нетерминалов, удовлетворяющих условию ||K|| < ||N||. При обнаружении такого разбиения, грамматику G можно преобразовать к виду G_K, а затем и применить к G_K ту же процедуру проверки-преобразования. В конце концов, на некотором шаге этого итеративного процесса будет построена неизбыточная грамматика G' эквивалентная G. Корректность описанной процедуры устранения избыточности следует из того, что на каждой итерации множество нетерминалов сокращается по-крайней мере на один символ.

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

Определение 4.3
КС-грамматика G = < N, Σ, P, S > называется нормальной (или НКС-грамматикой), если

(а) в P имеется правило S → #, причем в остальных правилах вывода терминал # не встречается;
(б) в P отсутствуют e-правила, за исключением, быть может, правила S → e;
(в) в P отсутствуют цепные правила;
(г) в P отсутствуют бесполезные правила;
(д) в N отсутствуют простые нетерминалы;
(е) G не является избыточной грамматикой.

Теорема.
Для любой КС-грамматики G существует HKC-грамматика G_н такая, что L(G_н) = L(G) ∪ {#}, где # - новый для грамматики G терминальный символ.

Доказательство. Существует цепочка преобразований исходной грамматики к искомому виду.

G G_а G_б G_в G_г G_д G_е = G_н

В данной цепочке считается, что грамматика G_x удовлетворяет требованиям (а)-(x) определения 4.3.

Преобразование G G_а определяется следующим образом: если G = < N, Σ, P, S' >, то G_а = < N ∪ {S}, Σ ∪ {#}, P ∪ (S → S' | #), S >, где # и S - символы, не встречающиеся в грамматике G. Очевидно, что L(G_а) = L(G) ∪ {#} и грамматика G_а удовлетворяет требованию (а).

Преобразования G_а G_б, G_б G_в, G_в G_г, G_г G_д, хорошо изучены [4]. В частности, известно, что каждое из этих преобразований
(1) сохраняет результаты ранее выполненных преобразований,
(2) является эквивалентным преобразованием КС-грамматик,
(3) сохраняет однозначность и праволинейность грамматики.

Преобразование G_д G_е реализует описанная выше процедура устранения избыточности. Очевидно, что эта процедура не отменяет свойства (а)-(д).

Следствие.
Для любой однозначной (праволинейной) КС-грамматики G существует однозначная (праволинейная) HKC-грамматика G_н такая, что L(G_н) = L(G) ∪ {#}, где # - некоторый новый терминальный символ.

Требование (а) из определения 4.3 позволяет упростить теоретические рассуждения по поводу особых свойств начального символа грамматики. Правило S → # из G_н всегда можно исключить, получив при этом остаточную грамматику эквивалентную G.

4.2.2 П-сети

Определение структуры КС-языков существенно использует аппарат П-сетей [51] специального вида.

Определение.
Двухполюсной сетью называется четверка < M, W, p, q >, где

(a)	M - множество вершин;
(б)	W - множество ориентированных ребер вида (m,m')X, причем метка ребра X есть символ некоторого алфавита;
(в)	p и q - выделенные вершины из M, которые называются соответственно входным и выходным полюсами сети. Вершины, отличные от полюсов, называются внутренними.

В сетях с помеченными ребрами каждому пути

Определение 4.4
Сеть T = < M, W, p, q > с помеченными ребрами порождает язык

Определение.
Подсетью сети T = < M, W, p, q > будем называть сеть T' = < M', W', p, q > такую, что
(1) M' ⊂ M, W' ⊂ W;
(2) для любого ребра из W' в сети T' существует путь [p,q], проходящий через это ребро.

Если в сети зафиксировать некоторое количество путей, соединяющих полюса, то вершины и ребра, входящие в эти пути, однозначно определяют некоторую подсеть.

Будем рассматривать взаимно однозначные функции переименования вершин r : M → M'. Для единообразия обозначений будем считать, что r(W) есть множество

Определение.
Сети < M, W, p, q > и < M', W', p', q' > будем называть изоморфными, если существует функция переименования r : M → M' такая, что r(p) = p', r(q) = q' и r(W) = W'.

Другими словами, под изоморфизмом сетей понимается такой изоморфизм, который сохраняет разметку ребер.

Определение.
    Однореберная двухполюсная сеть < {p,q}, {(p,q)_a}, p, q > является П-сетью.
    Если < M₁, W₁, p₁, q₁ >   и   < M₂, W₂, p₂, q₂ > - П-сети, то
и s-сеть < M₁ ∪ r_s(M₂), W₁ ∪ r_s(W₂), p₁, r_s(q₂) >,
и p-сеть < M₁ ∪ r_p(M₂), W₁ ∪ r_p(W₂), p₁, q₁ >
являются П-сетями для любых функций переименования

Соглашение.
В теоретических построениях, связанных с определением структуры КС-языков, будем предполагать, что вершины П-сетей задаются цепочками некоторого алфавита. При этом можно считать, что ребра также представляют собой цепочки символов. Скажем, ребру вида (α,β)_a соответствует цепочка (α,β,a) в алфавите, дополненном символами "(", "," и ")".

Определение.
Пусть T = < M, W, p, q > - сеть, и W ' - выделенное подмножество ребер из T. Кроме того, известно соответствие, по которому ребрам w из W ' однозначно сопоставляются некоторые П-сети < M_w, W_w, p_w, q_w gt;. Результатом подстановки в сеть T вместо ребер из W ' соответствующих П-сетей называется двухполюсная сеть < M_res, W_res, p, q >, в которой

Mres = ∪ rw(Mw) ∪ M, w ∈ W '

Wres = ∪ rw(Ww) ∪ W \ W ' w ∈ W '

и каждая функция переименования вершин сети T_w для w = (a,b)_x есть:

При некоторых условиях операция подстановки позволяет синтезировать новые П-сети из более простых элементов. Введем ряд специфических определений и обозначений, позволяющих анализировать структуру П-сетей.

В П-сети T = < M, W, p, q > выделим пару вершин p' и q' и обозначим через T(p',q') четверку < M', W', p', q' >, в которой M' и W ' составляют вершины и ребра сети T, принадлежащие хотя бы одному пути [p',q'].

Определение 4.5
Будем говорить, что пара вершин p' и q' определяет p-элемент сети T = < M, W, p, q >, если T(p',q') является p-сетью, и любой путь [p,q], содержащий внутренние вершины сети T(p',q'), проходит через p' и q'.

На p-элементах естественным образом определяется отношение вложенности.

Определение.
Будем говорить, что p-элемент T(p',q') вложен в p-элемент T(p'',q''), и писать T(p',q') ⊂ T(p'',q''), если все вершины первой сети являются вершинами второй сети.

Отношение вложенности порождает древовидную иерархию Д(T) p-элементов сети T. Корнем дерева Д(T) является сама сеть T. Вершинами дерева Д(T) являются p-элементы сети T.

Обозначим inn(T') - множество p-элементов, непосредственно вложенных в p-элемент T'.

Иерархия вложенности позволяет однозначно приписать значение глубины каждому p-элементу p-сети T. По определению глубина p-элемента T' есть глубина вершины T' дерева Д(T).

Пример.

Из определения 4.5 следует, что в любой П-сети T можно выполнить замену p-элемента T(p',q') на некоторое ребро (p',q')_x. Сеть, полученная в результате такой замены, по-прежнему остается П-сетью.

Определение.
Пусть T - р-сеть и n - некоторое число. Будем обозначать П(T,n) П-сеть, которая получается из T заменой всех ее p-элементов T(p',q') глубины n на ребро (p',q')_П, помеченное уникальным фиксированным символом П.

На содержательном уровне можно говорить, что сеть П(T,n) сохраняет внешнюю структуру сети T, а на местах несущественных деталей располагаются ребра-заглушки, помеченные специальным символом П.

Определение.
Будем полагать, что две p-сети T' и T'' связаны отношением ≈_n, и писать T' ≈_n T'', если p-сети П(T',n) и П(T'',n) изоморфны. В случае, когда сети T₁ и T₂ не связаны отношением ≈_n, будем писать T₁ T₂.

4.2.3 Структура КС-языков

Рассмотрим вопрос о соотношении КС-языков и П-сетей.

Определение.
Пусть G = < N, Σ, P, S > - НКС-грамматика. НКС-диаграммой t_A,0 (A ∈ N) называется П-сеть < M_A,0, W_A,0, p_A, q_A > вида:

НKC-диаграммы обладают рядом свойств.

Первое. В НКС-диаграммах отсутствуют ребра, помеченные символом e. Исключение составляет диаграмма t_S,0, которая может содержать ребро (p_S,q_S)_e.

Второе. Во всех НКС-диаграммах отсутствуют ребра (p_A,q_A)_B, где B ∈ N. (Другими словами, если ребро НКС-диаграммы помечено нетерминалом, то, по-крайней мере, одна из его вершин является внутренней.)

Третье. Все НКС-диаграммы являются p-сетями.

Перечисленные особенности являются всего лишь переформулировкой свойств (б), (в) и (д) определения 4.3. Остальные свойства НКС-грамматик проявляются на сетях более сложной структуры.

Будем обозначать:
— W[A] = {(m,m')_X ∈ W | X ∈ A} - множество ребер сети < M, W, p, q >, помеченных символами из алфавита A;
— V_A = W_A,0[N];
— t_w,1 = t_A,1, M_w,1 = M_A,1, .... , если ребро w помечено символом A.

Определение 4.6
Определимя для НКС-грамматики G = < N, Σ, P, S > семейство сетей { t_A,1 | A ∈ N, i ≥ 0 } следующим образом: для i ≥ сеть t_A,i+1 = < M_A,i+1, W_A,i+1, p_A, q_A > есть результат подстановки в НКС-диаграмму t_A,0 вместо каждого ребра w ∈ V_A соответствующей ему сети t_w,i.

В связи с определением 4.6 индукцией по i легко показать, что (при i ≥ 0 и A ∈ N)

• произвольная сеть t_A,i принадлежит классу p-сетей;
• inn(t_A,i+1) = { r_w(t_w,1) | w ∈ V_A }
  (Откуда следует, что в сети t_A,i любой p-элемент глубины k изоморфен сети t_B,i-k для некоторого B из N.);
• M_A,i ⊂ M_A,i+1 и W_A,i[Σ] ⊂ W_A,i+1[Σ];
• L(t_A,i) = L(G,A,i) ∪ L(G,A,i), где
  • L(G,A,i) - содержит все терминальные цепочки из { x | A =>^*_G x }, которым соответствуют деревья вывода глубины не более i+1;
  • L(G,A,i) - содержит все цепочки из { αBβ | A =>^*_G αBβ, B ∈ N }, которым соответствуют деревья вывода глубины i+1.

Определение 4.7
Для каждого нетерминала A НКС-грамматики определим сеть T_A = < M_A, W_A, p_A, q_A >, в которой

MA = ∪ MA,i, i ≥ 0

WA = ∪ WA,i[Σ]. i ≥ 0

Приведем свойства сетей T_A:

Таким образом, сеть T_S можно рассматривать, как структуру КС-языка.

Замечание.
Если G - однозначная НКС-грамматика, то все сети T_A и t_A,i являются однозначными.

Лемма 4.8
Для любой НКС-грамматики G = < N, Σ, P, S > сети из множества { T_X | X ∈ N } попарно неизоморфны.

Доказательство. Предположим, что в некоторой НКС-грамматике G, по-крайней мере, для двух нетерминалов X и Y сети T_X и T_Y изоморфны. Построим для этой грамматики разбиение нетерминалов K следующим образом: нетерминалы A и B относятся к одному классу K_C тогда и только тогда, когда сети T_A и T_B изоморфны. По предположению ||K|| < ||N||. Докажем, что разбиение K является согласованным.

Зафиксируем две произвольные изоморфные две сети T_A и T_B. Обозначим h - взаимно однозначное соответствие M_A → M_B, поддерживающее этот изоморфизм. Тогда h(M_A,0) = M_B,0. (Если предположить, что для некоторой вершины m_A ∈ M_A,0 вершина m_B = h(m_A) не принадлежит M_B,0, то m_B является внутренней вершиной для некоторой сети r_w(T_w), причем {p_w,q_w} ≠ {p_B,q_B}. В силу изоморфизма вершина m_A = g(m_B), где g = h^-1, также является внутренней вершиной некоторого p-элемента T_A(g(p_w),g(q_w)), причем {g(p_w),g(q_w)} ≠ {g(p_B),g(q_B)} = {p_A,q_A}. То есть m_A ∉ M_A, что противоречит сделанному предположению.)

Рассмотрим свойства взаимно однозначного соответствия h применительно к НКС-диаграммам t_A,0 и t_B,0.

Свойства (1)-(3) гарантируют согласованность разбиения K (см. определения 4.1 и 4.4).

Таким образом, грамматика G является избыточной, что не соответствует определению НКС-грамматик.

Следствие.
Для любой НКС-грамматики G существует число E(G) > 0 такое, что при j ≥ i ≥ E(G) сети множества { П(t_X,j,i) | X ∈ N } попарно неизоморфны.

Для заданной НКС-грамматики определим семейство П-сетей { T_S,i | i ≥ 1}.

Поскольку НКС-грамматика не содержит бесполезных правил вывода, то для любого i ≥ в сети T_S существует класс П-подсетей T, удовлетворяющих свойству T ≈_i t_S,i. Обозначим T_S,i наименьшую (по числу ребер) сеть из этого класса. (В случае нескольких наименьших сетей выбираем одну из них.)

4.3 Метод обобщения

Следствие из леммы 4.8 позволяет надеяться, что для восстановления НКС-грамматики можно ограничиться некоторой подсетью T_S,i. Покажем это.

Определение.
Пусть G = < N, Σ, P, S > - НКС-грамматика, n = E(G). Определим два класса П-сетей U(G) и UU(G), а также функцию u : U(G) → N.

(1)	П-сеть T принадлежит классу U(G) тогда и только тогда, когда T ≈n tA,n для некоторого A = u(T).
(2)	UU(G) = { T ∈ U(G) | inn(T) ⊂ U(G) }.

Базисом множества U(G) будем называть подмножество Б ⊂ UU(G) такое, что u(Б) = N и ||Б|| = ||N||.

Базисами множества U(Б) являются, в частности, множества

Нас будут интересовать функции именования f: U(G) → N', удовлетворяющие условию f(T) = f(T'), если T ≈_n T' (n = E(G)). Для того, чтобы построить функцию именования достаточно задать ее значения на некотором базисе, а затем доопределить ее с помощью отношения ≈_n. При таком подходе вычисление функции сводится к проверке на изоморфизм конечных П-сетей.

Поскольку функции именования однозначно определяют классы эквивалентности отношения ≈_n, то все эти функции эквивалентны друг другу с точностью до взаимно однозначного переименования множества значений. Поэтому в дальнейшем изложении будем использовать только одну функцию именования - функцию u. При этом все равенства цепочек справедливы с точностью до взаимно однозначного переименования нетерминалов.

Определение 4.9
Пусть G = < N, Σ, P, S > - НКС-грамматика, n = E(G), Б - базис класса U(G), T - сеть из UU(G). Определим:
— сеть t(u,T) как результат подстановки в сеть T вместо p-элементов T(m,m') ∈ inn(T) соответствующих ребер (m,m')_X, где X = u(T(m,m'));
— множество правил вывода P(u,Б), задающих грамматику G(u,Б),

Лемма 4.10
При условиях, заданных в определении 4.9, имеет место равенство P = P(u,Б).

Доказательство. Поскольку Б - базис класса U(G), то

Рассмотрим сеть t_X,n+1.

По определению класса UU(G) между сетями П(t_X,n+1,n+1) и П(T_X,n+1) существует отношение изоморфизма, которое, в частности, индуцирует изоморфизм сетей t(u,t_X,n+1) и t(u,T_X). Следовательно, L(t(u,T_X)) = L(t_X,0) = R(G,X). Таким образом:

Покажем, что базис класса U(G) можно построить по конечному фрагменту сети T_S.

Определение 4.11
Пусть T - П-сеть и n - некоторое число. Определим подмножество p-элементов Ф(T,n), удовлетворяющее трем условиям.

(1)	T ∈ Ф(T,n).
(2)	Если T' и T'' - пара различных сетей из Ф(T,n), то T' ≈n T''.
(3)	Если T'' ∈ inn(T') и T' ∈ Ф(T,n), то либо T'' ∈ Ф(T,n), либо T'' ≈n TB, для некоторой сети TB ∈ Ф(T,n).

Свойства (1) и (3) определяют множество Ф(T,n) как некоторую "сплошную" окрестность корня дерева Д(T). Очевидно, что по заданным T и n можно построить, по-крайней мере, одно множество Ф(T,n).

Лемма 4.12
Пусть G = < N, Σ, P, S > - НКС-грамматика, n = E(G) и
       T - некоторая П-сеть такая, что T ≈_i t_S,i при i > ||N||+n
Тогда Ф = Ф(T,n) есть базис класса U(G).

Доказательство. Поскольку в определении множества Ф(T,n) используется только отношение изоморфизма, то искомое утверждение достаточно показать для T = t_S,i.

В обозначениях p-элементов будем использовать [первые] нижние индексы, совпадающие со значениями глубины соответствующих p-элементов. Кроме того, обозначим

Последовательно докажем следующие утверждения:

(1) В соответствии со свойствами сети t_S,i каждая сеть T' ∈ V изоморфна некоторой сети t_A,i-k. Откуда следует, что T'_k ≈_i-k t_A,i-k, причем i-k > n. Последнее неравенство гарантирует, что V ⊂ UU(GG).

(2) Положим n' = ||N|| и рассмотрим произвольный p-элемент T'_n' и связанную с ним последовательность вложенных p-элементов

Перекодируем эту последовательность с помощью функции u:

(3) Предположим, что существует непустое множество нетерминалов N' = N \ f(Ф). По определению множества Ф(T,n) S ∉ N'.

Зафиксируем некоторый нетерминал A ∈ N'. Поскольку НКС-грамматика не содержит бесполезных правил, то существует p-элемент T'_k ∈ V такой, что u(T'_k) = A. Рассмотрим последовательность непосредственно вложенных p-элементов

Введем обозначения для пары смежных сетей: B = A_j-1, T^B = T_j-1, C = A_j, T^C = T_j. Так как B ∈ N', то существует сеть ∈ Ф такая, что u() = B.

Поскольку {T^B,} ⊂ V ⊂ UU(G), то T^B ≈_n+1 . Этот изоморфизм однозначно сопоставляет p-элементу T^C ∈ inn(T^B) некоторый элемент ∈ inn(), причем u() = C.

Итак, имеем: ∈ Ф, ∈ inn(). По определению множества Ф среди его элементов найдется сеть такая, что   ≈_n  , то есть u() = u() = C. Следовательно,

(4) В данном случае равенство ||Ф|| = ||N|| является следствием определения Ф(u,T) и свойств числа E(G).

Определение 4.13
Пусть T - некоторая П-сеть.
Определим множество грамматик G(T) = { G(f_n,Ф_n) | n = 1, ..., глубина(T)+1 }, где
Ф_n = Ф(T,n) - множество сетей, удовлетворяющих определению 4.11,
f_n - некоторая функция именования, заданная на Ф_n;
G(f_n,Ф_n) - грамматика, построенная согласно определению 4.9.

Теорема 4.14
Пусть G = < N, Σ, P, S > - НКС-грамматика и T - П-сеть изоморфная некоторой сети T_S,i для i ≥ ||N|| + E(G). Тогда множество G(T) содержит грамматику G' такую, что L(G') = L(G).

Доказательство. Прежде всего заметим, что

Замечание.
Определение 4.13 можно рассматривать как метод вычисления множества грамматик G(T). При таком подходе это определение следует дополнить предварительным и заключительным преобразованиями. Предварительное преобразование модифицирует множество ребер сети T = < M, W, p, q >: W = W ∪ { (p,q)_# }. (Напомним, что наличие правила S → # является обязательным свойством НКС-грамматик.) Заключительное преобразование удаляет из построенных грамматик G(f_n,Ф_n) правило S → #.

4.4 Методы структурирования

Определение 4.13 фактически задает метод обобщения для произвольных КС-языков. В соответствии с теоремой 4.14 нас будет интересовать задача восстановления сети T_S,n (с точностью до отношения ≈_n) по некоторому множеству предложений Ω = Ω_i(n), принадлежащему полной положительной последовательности образцов. Подходы к решению поставленной задачи определяются дополнительными ограничениями на класс языков источника. Естественно, что самые жесткие ограничения приводят к наиболее эффективным процедурам восстановления. Рассмотрим три метода восстановления, ориентированные на разные подклассы КС-языков.

4.4.1 Восстановление регулярных языков

Язык является регулярным, если он порождается праволинейной грамматикой [4].

Замечание 4.15
Выберем уникальный символ ¶. Задачу восстановления регулярных языков достаточно рассмотреть для случая модифицированных образцов

Применительно к языкам L_и,v известные результаты [4] теории регулярных языков позволяют утверждать, что
для любого языка L_и,v существует порождающая его праволинейная грамматика G^v, в которой

(1)	все правила вывода имеют вид A → axB или A → ax для некоторого x из Σ*;
(2)	для различных A-правил A → aα и A → bβ имеет место неравенство a ≠ b.

Очевидно, что НКС-грамматика G_н,v, построенная по грамматике G^v, сохраняет свойства (1) и (2). А это, в свою очередь, позволяет сформулировать два характеристических свойства П-сети T = T_S, построенной по НКС-грамматике G_н,v.

Свойство праволинейности. Выходные полюса всех p-элементов сети T совпадают с выходным полюсом самой сети T.

Свойство детерминированности. Любые два ребра (m,m')_a и (m,m")_b, исходящие из одной вершины m, помечены различными символами a и b, если m' ≠ m".

Свойства праволинейности и детерминированности позволяют восстановить любую подсеть T' сети T по известному множеству цепочек Ω = L(T').

Определение 4.16
Пусть Ω - множество предложений. Определим сеть TRL(Ω) следующим образом:
(а) множество вершин M = { {x} | xy ∈ Ω для некоторого y ∈ Σ^* } ∪ {Ω};
(а) множество ребер W = { (m,m')_a | x ∈ m ∈ M, xa ∈ m' ∈ M };
(а) входной полюс p = {e};
(а) выходной полюс q = Ω.

Если все предложения из Ω имеют концевой маркер, то сеть TRL(Ω) (1) удовлетворяет свойству детерминированности; (2) по сути дела, представляет собой дерево со "склеенными" концевыми вершинами. (Отсюда, в частности, вытекает, что TRL(Ω) - П-сеть.) Алгоритмически построение сети TRL(Ω) сводится к левой факторизации [14] множества предложений из Ω (см. пример 5.9).

Лемма 4.17
Пусть G_н,v = < N, Σ, P, S > - праволинейная НКС-грамматика, порождающая язык L_и,v, и Ω - подмножество предложений из L_и,v такое, что L(T_S,n) ⊂ Ω для некоторого n. Тогда TRL(Ω) ≈_n T_S,n.

Метод 4.18 (Восстановление регулярных языков).
Шаг 1 (Структурирование). По заданному образцу Ω, используя определение 4.16, построить сеть T = TRL(Ω).
Шаг 2 (Обобщение). По сети T, используя определение 4.13, построить множество решающих грамматик G(T).

Теорема 4.19
Задача грамматического вывода разрешима для регулярного языка источника L_и, полной положительной последовательности образцов { Ω_i | i ≥ 1 } и метода восстановления 4.18.

Доказательство. В силу замечания 4.15, утверждение теоремы достаточно показать для некоторого регулярного языка источника L_и,v. Зафиксируем такой язык и рассмотрим порождающую его грамматику G_н,v = < N, Σ, P, S >.

Положим n = ||N|| + E(G_н,v) и m = max { |x| | x ∈ L(T_S,n) }.

Поскольку последовательность образцов является полной положительной, то среди ее членов найдется образец Ωi(m) такой, что

Из леммы 4.17 следует, что TRL(Ω_i(m)) ≈_n T_S,n. В силу теоремы 4.14 множество G(TRL(Ω_i(m)) содержит грамматику G', такую, что L(G') = L(G_н,v) = L_и,v.

Идея использовать свойство детерминированности для восстановления регулярных языков была впервые сформулирована в работах Дж.Фельдмана и др. [55]. Метод 4.18 можно рассматривать как уточненную версию метода Фельдмана, гарантирующую восстановление однозначной грамматики.

4.4.2 Восстановление однозначных контекстно-свободных языков

В отличии от регулярных языков, при восстановлении КС-языков общего вида приходится опираться на свойства гипотетической грамматики, порождающей язык источника. Общий подход к восстановлению КС-языков предполагает, что класс НКС-грамматик можно дополнительно ограничить.

Определение [4]
Нетерминал A КС-грамматики G называется рекурсивным, если A =>⁺_G αAβ ; в противном случае нетерминал A называется нерекурсивным. Грамматика называется нерекурсивной, если она не содержит рекурсивных нетерминалов.

Методы устранения нерекурсивных нетерминалов известны [4]. Однако, в результате применения такого преобразования к НКС-грамматике, вновь построенная грамматика может стать избыточной. В связи с этим необходимо заново обратиться к процедуре устранения избыточности. В дальнейшем будем рассматривать только такие НКС-грамматики, в которых все нетерминалы, отличные от начального, являются рекурсивными.

В терминах структуры КС-языков дополнительное ограничение позволяет утверждать, что в любой сети T_A (A ≠ S) найдется собственный p-элемент T', изоморфный T_A. В этом случае можно рассчитывать, что некоторая конфигурация ребер, встречающаяся во внешней структуре сети T_A, будет циклически повторяться для ее p-элементов. Будем использовать это наблюдение для восстановления конечного фрагмента сети T_S. Однако прежде всего, построим метод выявления особых предложений языка источника, выводимых непосредственно из начального символа.

Определение. Пусть G = < N, Σ, P, S > - НКС-грамматика. Определим
— множество предложений ост(G) = {x ∈ Σ^* | x ∈ R(G,S), x ≠ #};
— множество правил вывода осн(P), задающих грамматику осн(G): осн(P) = P \ (S → ост(G)).

Напомним, что # - специальный символ НКС-грамматик. Определим для него сеть T_#, состоящую из единственного ребра (p,q)_#.

Связь между однозначной грамматикой G и соответствующей грамматикой осн(G) очевидна: ост(G) = L(G) \ L(осн(G)). Кроме того, осн(осн(G)) = осн(G).

Определение 4.20
Пусть G = < N, Σ, P, S > - НКС-грамматика и Ω - конечное множество цепочек. Определим
— множество предложений ост(G,Ω) = { x ∈ Ω | x - не выводима в G };
— множество правил вывода доо(P,Ω), задающих грамматику доо(G,Ω):

доо(P,Ω) = P ∪ (S → ост(G,Ωя0)).

Если для однозначной НКС-грамматики G, множество Ω удовлетворяет условию ост(G,Ω) ⊂ Ω ⊂ L(G), то G = доо(осн(G)Ω).

Перейдем к вопросу о восстановлении основной части правил НКС-грамматики.

Соглашение.
Зарезервируем символ R для обозначения множеств, элементами которых являются пары цепочек (x,y) из некоторого алфавита. Символом F будем обозначать множества, элементами которых являются R-множества.

Определение.
Пусть F = {R₁,..., R_k}. Определим
— множество ребер

Определение.
Пусть T = < M, W, p, q > - П-сеть. Определим
— для заданной вершины m ∈ M множество

Определение.
Определим сумму П-сетей T_i = < M_i, W_i, p_i, q_i > ( i=1,...,n ), будем обозначать ее ⊕{ T₁ , ..., T_n }, как сеть < F, MP(F), R_вх, R_вых >, где

(а)	n  F= МУ({ ∪ F(Ti)) ∪ { Rвх, Rвых }; i = 1
(б)	n  Rвх = ∪ R(Ti,pi); i = 1
(в)	n  Rвых = ∪ R(Ti,qi). i = 1

Лемма 4.21
Пусть T - однозначная П-сеть и T₁, ..., T_n - некоторое множество ее подсетей. Тогда ⊕{ T₁, ..., T_n} - П-сеть.

В связи с грамматиками нас будут интересовать подсети простой циклической структуры. Прежде чем перейти к определению этих сетей, договоримся обозначать на рисунках путь [m,m']_x в виде стрелки с меткой x. В случае x = e стрелка вырождается в вершину m.

Определение.
Будем называть Л-сетью (бесконечную) сеть вида:

Определение.
Пусть T = < M, W, p, q > - Л-сеть и k - некоторое целое число. Будем обозначать [T]_k конечную подсеть сети T, содержащую все пути [p,q]_x такие, что

Лемма 4.22
Пусть n, k - целые числа и G = < N, Σ, P, S > - однозначная НКС-грамматика, удовлетворяющая условию G = осн(G). Тогда существует конечное множество { T₁, ... T_m} Л-подсетей сети T_S такое, что ⁿ

Доказательство теоремы состоит в конструировании множества Л-подсетей с заданными свойствами. Корректность применения отношения ≈_n к сети ⊕{ T_#, [T₁]_k(1) ,..., [T_m]_k(m) } следует из леммы 4.21.

Лемма 4.22 дает подход к восстановлению однозначных НКС-грамматик по известному образцу Ω и параметру k_inf.

Метод 4.23 (Восстановление однозначных КС-языков)
Шаг 1. Построить множество сетей

(а) (Структурирование) построить сеть T = ⊕(T ∪ {T_#});
(б) (Обобщение) используя определение 4.13, построить множество грамматик G(T);
(в) используя определение 4.20, построить подмножество решающих грамматик {доо(G,Ω) | G ∈ G(T)}.

Теорема.
Задача грамматического вывода разрешима для однозначного КС-языка источника L_и, полной положительной последовательности образцов {Ω_i | i ≥ 1} и метода восстановления 4.23.

Доказательство. Зафиксируем произвольный однозначный КС-язык источника L_и и некоторую соответствующую ему НКС-грамматику G = < N, Σ, P, S >. Кроме того, зафиксируем некоторое значение параметра k_inf.

Рассмотрим сеть T_S,n для n = ||N|| + E(G).

Из леммы 4.22 следует, что для сети T_S,n существует восстанавливающий набор k-Л-подсетей [T₁]_k(1), ..., [T_m]_k(m). Положим I = max { J₀, J₁, ..., J_m}, где
J₀ = max {|x| | x ∈ ост(G) },
J_j = max {|x| | x ∈ L([T_j]_k(j)) } (j=1, ..., m).

Так как последовательность образцов является полной положительной, то среди ее членов найдется образец Ω_i(I) такой, что { x ∈ L | |x| ≤ I} ⊂ Ω_i(I). При этом, L([T_j]_k(j)) ⊂ Ω_i(I) для любого j = 1, ..., m.

Из определения множества КЛ (см. шаг 1 метода 4.23) следует, что КЛ(Ω_i(I),k_inf) содержит сеть T' изоморфную [T_j]_k(j) ( j=1, ..., m ).

Поскольку операция ⊕ использует исключительно разметку ребер, то на шаге 2.а (в частности) будет построена сеть

Из теоремы 4.14 следует, что среди грамматик G(T), построенных на шаге 2.б, найдется грамматика, эквивалентная G^ост.

Выбор числа I гарантирует, что ост(G) ⊂ Ω_i(I). Следовательно, грамматика доо(осн(G),Ω_i(I)) эквивалентна G.

Метод 4.23 является параметрическим, причем формальная применимость метода не зависит от значения параметра k_inf. По своему смыслу k_inf задает минимальное количество конкретных проявлений, достаточное для принятия решения о существовании той или иной закономерности. С практической точки зрения, варьируя параметром k_inf, можно сократить количество k-Л-сетей, построенных на первом шаге, что позволит сократить перебор на шаге 2. В любом случае значение k_inf зависит от контекста применения метода восстановления.

4.4.3 Эвристический метод восстановления контекстно-свободных языков

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

Для НКС-грамматики G = < N, Σ, P, S > определим два класса цепочек:

Приведем три свойства однозначных НКС-грамматик.

Свойство 1. Множество { L(G,α) | α ∈ R(G,S) } образует наименьшее разбиение языка L(G) подмножествами L(G,β), где β ∈ RR(G,S).

Свойство 2. Пусть α = z₀A₁z₁...A_nz_n - цепочка из RR(G,S) и n > 1. Тогда строковое уравнение (относительно A₁, ..., A_n)

Первое свойство задает процедуру выявления множества R(G,S) из более широкого множества цепочек RR(G,S). Второе свойство позволяет перейти от восстановления множества R(G,S) (по известному образцу Ω) к восстановлению множеств R(G,A_i) (по множеству решений типа y_i).

Свойство 3. Пусть α = z₀A₁...A_nz_n - цепочка из RR(G,S) и n > 1. Тогда существуют, по-крайней мере, две цепочки x₁ и x₂ из L(G,α) такие, что правильные решения (y₁₁, ..., y_1n) и (y₂₁, ..., y_2n) соответствующих строковых уравнений z₀A₁z₁...A_nz_n = x₁ и z₀A₁z₁...A_nz_n = x₂ удовлетворяют условиям y_1i ≠ y_2i (i=1,...,n).

Свойство 3 дает подход к формированию некоторого подмножества цепочек из RR(G,S).

Рассмотрим две подзадачи, которые решаются в ходе восстановления грамматик эвристическим методом.

Задача 4.24 (Задача восстановления общей структуры двух цепочек).
Дано. Две цепочки символов x₁ и x₂.
Требуется. Построить множество SV(x₁,x₂) цепочек вида z₀A₁z₁...A_nz_n, удовлетворяющих условиям:

(1)	уравнения z0A1z1...Amzm = x1 и z0A1z1...Amzm = x2 имеют по-крайней мере по одному решению (y11, ..., y1n) и (y21, ..., y2n), причем yij ≠ e (i=1,2; j=1,...,n);
(2)	если цепочки α = z'0A1z'1...Amz'm   и   β = z0A1z1...Amm удовлетворяют условию (1) и |z'0z'1...z'm| < |z0z1...zm|, то α ∉ SV(x1,x2).

Условию (1) всегда удовлетворяют тривиальные, но бесполезные цепочки, состоящие из единственного нетерминала A₁. Условие (2) позволяет найти "самое нетривиальное" решение и, в частности, гарантирует равенство SV(x,x) = { x }, которое должно выполняться по смыслу задачи. В общем случае задача 4.24 не имеет единственного решения, например, SV(ab,aab) = {A₁b, aA₁}.

Метод решения задачи 4.24 для цепочек x₁ = a₁...a_n    и    x₂ = b₁...b_m существенно использует ориентированный граф специального вида. Вершинами графа являются элементы множества {(i,j) | a_i = b_j}, а множество ребер образуют все пары вершин ((i,j),(i',j')), для которых либо i' = i+1 и j' = j+1, либо i' > i+1 и j' > j+1. В том же случае, когда граф построить не удается, в качестве решения принимается множество цепочек { A₁...A_i | i = 2, ..., min(m,n) }.

В соответствии с процедурой выявления множества R(G,S), для каждой цепочки β ∈ RR(G,S) необходимо построить множество L(G,β) или его конечное подмножество Ω(β).

Задача построения множества Ω(β) по образцу Ω и цепочке β обладает двумя особенностями. Во-первых, эта задача может иметь несколько решений. Во-вторых, при решении именно этой задачи появляется возможность пополнить заданный образец новыми предложениями. При этом необходимо задать априорную оценку полноты образца - параметр ρ.

Будем полагать, что множество Ω(β) задается в виде L(G(Ω,β)) ∩ Ω, где G(Ω,b) - нерекурсивная грамматика, удовлетворяющая некоторым требованиям.

Условие 4.25

(1)	Грамматика G(Ω,β) для β = z0A1z1...Anzn имеет вид: S → β Ai → Ωi   (i=1, ..., n), где Ωi ∈ Σ+ и ||Ωi|| > 1
(2)	Для любой цепочки yi ∈ Ωi существуют цепочки yj ∈ Ωj (j =1, ..., i-1,i+1, ..., n) такие, что z0y1z1...ynzn ∈ Ω
(3)	Грамматика G(Ω,β) является однозначной
(4)	||Ω(β)||  ≥ ρ     где ρ - параметр метода ||L(G(Ω,β))||
(5)	Множества Ωi (i=1, ... ,n) нельзя пополнить новыми цепочками с сохранением условий (1)-(4).

Задача 4.26
Дано. Образец Ω, цепочка β и параметр ρ ∈ (0,1].
Требуется. Построить GSV(Ω,β) - множество всех грамматик G(Ω,β), удовлетворяющих условию 4.25.

Задача 4.26 решается перебором подмножеств Ω_i,all ⊂ Ω_i (i=1,...,n), где множество Ω_i,all есть

Определим две операции над нерекурсивными грамматиками

Пусть Ω - некоторое множество предложений и ρ - число из (0,1]. Определим множество грамматик GSV(Ω) как результат следующей последовательности вычислений:

Приведем метод структурирования образца Ω. Результатом вычисления является множество нерекурсивных грамматик G = G(Ω,ρ), где ρ - параметр метода.

Метод 4.27 (Эвристический метод структурирования)
Шаг 1. Положить G = { < {S}, Σ, S → Ω, S > }.
Шаг 2. Если среди грамматик множества G найдется грамматика G такая, что для некоторого нетерминала A    R(G,A) ⊂ Σ^* и R(G,A) - нетривиальный образец, то

(a) преобразовать множество G G = (G \ {G}) ∪ { п(G,A,G') | G' ∈ GSV(R(G,A)) }; (б) повторить шаг 2.

Каждую нерекурсивную грамматику из множества G(Ω,ρ) можно очевидным образом преобразовать в конечную П-сеть. При этом появляется возможность применить к ней метод обобщения 4.13 и построить множество решающих КС-грамматик общего вида.

С точки зрения разрешимости задачи грамматического вывода (методом 4.27), рассчитывать на восстановление КС-грамматики G_и = < N, Σ, P, S > можно лишь в том случае, когда образец содержит достаточное количество предложений глубиной вывода не более ||N|| + E(G_и).

Главный недостаток эвристического метода состоит в том, что множество G(Ω,ρ) может содержать слишком много различных грамматик. Причиной тому является независимость друг от друга множеств GSV(R(G,A)). Вместе с тем, совокупность этих множеств можно рассматривать как некоторую систему альтернатив (см. определение 2.1), в которой двум грамматикам сопоставляется один и тот же факт, если их внешние структуры совпадают. (Речь идет об отношении типа ≈.) При таком подходе, на этапе структурирования генерируются лишь те грамматики, которым соответствуют наборы фактов из класса распознавания системы альтернатив. В конечном итоге, описанная модификация эвристического метода позволяет отсечь "неинтересные" грамматики, по-разному структурирующие одинаковые или сходные образцы.

Методы восстановления формальных грамматик используется:
— для синтеза схем управления (п. 5.4);
— в методе доводки имен атрибутов (п. 5.5).