r2 - 28 Jul 2005 - 09:31:03 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > FuturePlans > SpecR2 > Algorithms > OptTheorem > RecAlg

Aлгоритм распознавания YES [Q] = <0>

Конечное множество первичных спецификаторов <* P1, P2, ..., PN *>, где N >= 2, является разложением первичного спецификатора P, если
YES [P] = YES [P1] + YES [P2] + ... + YES [PN].

Очевидно, что если <* P1, P2, .., PN *> - разложение первичного спецификатора P, то YES [P [I]] SUBSET YES [P] для I = 1, 2, ..., N.

Если для любого первичного спецификатора P и любого конечного множества первичных спецификаторов P1, P2, ..., PN можно распознавать истинность соотношения YES [P] = YES [P1] + YES [P2] + ... + YES [PN], то можно построить и алгоритм распознавания соотношения YES [Q] = <0>.

Если Q не содержит положительные члены, т.е. Q = (P1) (P2) ... (PN), где N >= 0, то YES [Q] = YES [< >] - YES [P1 P2 ... PN] = <0>

Предположим, что Q содержит хотя бы один положительный член. Тогда его можно представить в виде
Q = (P1) (P2) ... (PN) P R.
Получаем YES[Q] = YES [(P1) (P2) ... (PN)] + YES [P R] - NO [(P1) (P2) ... (PN)] = YES [P R] - YES [P1 P2 ... PN] = [YES [P] - YES [P1 P2 ... PN]] + [YES [R] - YES [P1 P2 ... PN]] = [YES [P] - YES [P1 P2 ... PN]] + YES [(P1) (P2) .. (PN) R] .

Таким образом, YES [Q] = <0> <=> [YES [P] - YES [P1 P2 ... PN]] = <0>] & [YES [(P1) (P2) ... (PN) R] = <0>]

Поскольку (P1) (P2) ... (PN) R короче, чем Q, для распознавания истинности соотношения YES [(P1) (P2) ... (PN) R] = <0> можно рекурсивно применять тот же самый алгоритм.

Теперь рассмотрим соотношение YES [P] - YES [P1 P2 ... PN] = <0>

Если сушествует хотя бы одно P[I], такое что YES[P] SUBSET YES[P[I]], то YES[P] - YES [P1 P2 ... PN] = <0>.

Если YES[P[I]] * YES[P] = <0> для некоторого P[I], то можно вычеркнуть P[I] из P1 P2 ... PN.

Приходим к задаче распознавания YES[P] - YES[P1 P2 ... PN], где для всех I = 1,2, ..., N верно YES[P[I]] SUBSET YES[P]. При таких ограничениях это условие равносильно YES [P] = YES [P1] + YES [P2] + ... + YES [PN], то есть проверке того, что <* P1, P2, ... PN*> является разложением первичного специфиактора P. Эту проверку по предположению делать умеем.

Замечание.

Если рассмотреть множество первичных спецификаторов языка Рефал, то оказывается, что распознавание того, что <* P1, P2, ..., PN *> является разложением P не составляет труда, послольку разложения имеют только первичные спецификаторы W, S, D, L.

YES[W] = YES[S B]
YES[S] = YES[O F N R]
YES[D] = YES['0123456789']
YES[L] = YES['ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'БГДЖЗИЙЛПУФЦЧШЩЫЬЭЮЯ']

-- Luba Parmyonova - 25 Jul 2005
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback