Сборник научных трудов под редакцией доктора физико-математических наук А. Н. Горбаня красноярск кгту



страница6/32
Дата09.08.2018
Размер2.19 Mb.
#43456
ТипСборник
1   2   3   4   5   6   7   8   9   ...   32

3. Модели выполнения программы

Элементарные события в кинетической машине Кирдина происходят недетерминированно и параллельно. Предлагаются некоторые простые варианты модели выполнения программы P .


3.1. Последовательная модель

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



Если элементарные события и одновременно допустимы для ансамбля , то оба они могут служить продолжением выполнения программы:



и , где ансамбли и , вообще говоря, различны. Таким образом, для одной программы возможны различные временные ряды ансамблей. Если программа финитна, то все эти ряды конечны. В противном случае среди всех рядов выполнения программы существует бесконечный ряд. Для детерминированной программы все финальные ансамбли, порожденные различными рядами элементарных событий одинаковы.
3.2. Параллельно-последовательная модель

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



Разбиение на множества совместных событий S* для данного ансамбля M неоднозначно. Различные для данного ансамбля M приводят к различным ансамблям Mi . Следовательно, такой временной ряд совместных множеств элементарных событий также неоднозначен.



Пример. Пусть программа P для кинетической машины Кирдина состоит из одной команды и имеет следующий вид: .

Ансамбль M отождествляем с функцией FM:



FM (AK)=1, FM (BK)=1, FM (QA)=1, FM (QB)=1.

Для таких программ и ансамбля возможны четыре допустимых события, которые определяются изымаемыми ансамблями над следующими словами:



  1. Слова AK, QA определяют элементарное событие S1;

  2. Слова AK, QB определяют элементарное событие S2;

  3. Слова BK, QA определяют элементарное событие S3;

  4. Слова BK, QB определяют элементарное событие S4.

Нетрудно заметить, что не все из этих допустимых событий совместны. Выпишем полный список множеств совместных элементарных событий:

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

Множество элементарных событий, к которому нельзя добавить ни одного допустимого события, не теряя совместности, назовем максимальным множеством совместных событий . В предыдущем примере множества и являются максимальными множествами совместных событий. То есть к исходному ансамблю M может быть применено два разных максимальных множества совместных событий, которые порождают различные ансамбли. Мы видим, что максимальная параллельно-последовательная модель также не однозначна. Переход от ансамбля M к некоторому ансамблю M’ однозначно определяется только в следующих случаях:



  • когда ансамблю M и программе P соответствует ровно одно допустимое событие;

  • (для максимальной параллельно-последовательной модели) когда весь набор допустимых событий для ансамбля M и программы P является одновременно совместным.

4. Программы, состоящие из одной команды



4.1. Распад

Рассмотрим программу, состоящую из одной команды вида



uvw  uf + gw.
Применимость

Эта программа применима к ансамблю M, если существуют такие цепочки u, wL* , что FM(uvw) > 0 .


Финитность

Лемма 1. Программа Р, состоящая из одной команды распада не будет финитной, если vf или vg .

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

Пример. uAwuAB+BAw. Программа применима к любому ансамблю, хотя бы одно слово которого содержит символ А. При каждом распаде такого слова будут порождаться еще два слова, к которым применима эта программа, поэтому такая программа не будет финитной.

Лемма 2. Программа Р, состоящая из одной команды распада не будет финитной для ансамбля M, если

1) существует два, возможно одинаковых разбиения цепочки v=a1b1=a2b2;

2) f=b1b2x, g=ya1a2, где x и y– некоторые фиксированные цепочки;

3) Существует слово uvw (FM(uvw) > 0) такое, что u=u1a1 или w=b2w1.



Доказательство. По условиям леммы:

v=a1b1=a2b2, ,

FM(u1a1vw) > 0 или FM(uvb2w1) > 0.

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



Разберем распад слова u1a1vw:

  1. {u1a1vw}{u1a1b1b2x, ya1a2w};

  2. к слову u1a1b1b2x программа применима, т.к. v=a1b1: {u1a1b1b2x}{u1 b1b2x, ya1a2b2x};

  3. к слову ya1a2b2x программа применима, т.к. v=a2b2: {ya1a2b2x}{ ya1 b1b2x, ya1a2x}.

  4. слово ya1b1b2x содержит цепочку a1b1b2, как и слово u1a1b1b2x, распад которого разбирался в пункте 2). Это слово породит слово, содержащее цепочку a1a2b2 , распад которого разбирался в пункте 3). И так бесконечно на каждом шаге распада будут поочередно порождаться слова, содержащие цепочки a1b1b2 или a1a2b2.

Теперь разберем распад слова uvb2w1:

  1. { uvb2w1}{u b1b2x, ya1a2b2w1};

  2. слово ya1a2b2w1 содержит цепочку a1a2b2, оно, как и в предыдущем случае, породит слово, содержащее цепочку a1b1b2 и т. д.

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

Программа Р, состоящая из одной команды распада финитна для ансамбля M, если

I. vf, vg

II. для любых двух разбиений v=а1b1= а2b2 , где возможно a1=a2 и b1=b2, хотя бы одно из трех условий не выполняется:

1. f=b1b2f1 , где f1 – произвольная фиксированная цепочка

2. g=g1a1a2, где g1 – произвольная фиксированная цепочка

3. Существует слово uvw, FM(uvw) > 0 такое, что

u=u1a1 или w=b2w1, где u1 и w1 –произвольные цепочки.
Д
оказательство.
Рассмотрим произвольное слово вида uvwM. Построим для него в виде двоичного дерева вывод всех возможных слов. Во второй строчке каждого узла дерева будем обозначать условия, при которых к данному слову применима программа распада, в третьей строчке будет вид данного слова при этих условиях. Потомок наследует условия всех своих предков. Стрелкой влево будем показывать слово вида uf , стрелкой вправо – gw . Правую и левую ветви дерева приведем отдельно.

Д
адим пояснения к схемам. Самая левая ветвь максимально будет иметь длину равную при условии, что подцепочка u имеет вид a1...a1a2, в остальных случаях эта ветвь будет короче. Вправо на каждом шаге она будет порождать слово gf1, условия распада которого аналогичны ветви 1.2. Ветвь 1.2 вправо максимально будет иметь длину равную при условии, что подцепочка f имеет вид b1b2...b2, в остальных случаях эта ветвь будет короче.

Влево на каждом шаге ветвь 1.2 будет порождать цепочки вида g1b1b2...b2f2 , которые получены при условии f=b1b2f2, а их распад возможен только в случае если g=g2a1a2, а это противоречит условиям критерия.

Правая ветвь двоичного дерева симметрична с точностью до переобозначений.

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

Пример. Нефинитная программа:

Пусть слово aabM.



aab{abb,aa};

abb{bb,aab}.

Получили слово aab, с которого начали. К нему данная программа также применима.


Детерминированность.

Программа не будет детерминированной, если в исходном ансамбле M0 или в одном из ансамблей, полученных одним или несколькими элементарными событиями на ансамбле M0, существует цепочка, из которой вычленение подцепочек v происходит неоднозначно. Это может происходить в тех случаях, когда один или несколько символов из начала цепочки v содержится в её конце в том же порядке.

Пусть цепочка v включена в слово h (FM(h)>0) более одного раза, не пересекаясь. Т.е. слово h можно представить в виде u1v(1)u2v(2)…unv(n)w, где n– число включений v в h. Элементарные события, происходя в любом порядке, разобьют слово h на n+1 слова: u1f, gu2f, … , gunf, gw.
Критерий детерминированности распада

Программа распада недетерминирована, если существует разбиение цепочки v=aba и выполняется хотя бы одно из условий:

1. u,w такие, что FM(uababaw)>0;

2. f=xababay или g=xababay, где x, y – фикс. цепочки;

3. f=df1 , u1,w такие, что FM(u1cvw) > 0 ,где cd=ababa;

4. g=g1c ,  u,w1 такие, что FM(uv dw1) > 0, где cd=ababa.

В остальных случаях распад детерминирован.

Доказательство. По условию uabaw uf+gw.

1. u,w такие, что FM(uababaw)>0. К слову uababaw распад применим двумя способами:



uababaw uf+gbaw и uababaw uabf+gw, что приведет к двум различным ансамблям. Следовательно, в этом случае распад недетерминирован.

2. f=xababay или g=xababay, где x, y – фикс. цепочки.

Команда распада имеет один из следующих видов:

uabaw  uxababay + gw;

uabaw uf+gxababay;

uabaw uxababay+gx1ababay1.

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

3. f=df1, u1,w такие, что FM(u1cvw) > 0 ,где cd=ababa.

Здесь cd – это некоторое, возможно, другое разбиение цепочки ababa.

Команда распада принимает вид:

uabaw udf1+gw.

Применением программы к слову u1cvw получаем два слова u1cdf1 и gw.



u1cdf1= u1ababaf1, а применение распада к этому слову недетерминированно (см. пункт 1)

4. g=g1c, существуют u,w1 такие, что FM(uvdw1) > 0, где cd=ababa.

Команда распада принимает вид:

uabawuf+g1cw.

Применением программы к слову uvdw1 получаем два слова uf и g1cdw.



g1cdw=g1ababaw, а применение распада к этому слову недетерминированно (см. пункт 1)

Если существует разбиение цепочки v=aba, но не выполняется ни одно из условий 1)-4), то в исходном ансамбле, а также во всех ансамблях, полученных элементарными событиями из исходного, не появляется слова, содержащего цепочку ababa. Следовательно, такой распад также будет детерминирован.

Пусть цепочку v невозможно представить в виде цепочки aba, тогда невозможны пересекающиеся включения v ни в какое слово. Следовательно, невозможна недетерминированность ни для какого ансамбля.

Критерий детерминированности распада доказан.



Пример. uABABw uf + gw , FM(ABABAB)>0.

Цепочка v представима в виде разбиения aba: a=AB, b– пустая цепочка. Слово ABABAB удовлетворяет условию 1) критерия, следовательно, распад этого слова будет недетерминирован. Действительно, из слова ABABAB можно получить два различных ансамбля применением команды распада:



FM1(f)=1, FM1(gAB)=1;

FM2(Abf)=1, FM2(g)=1.

Ансамбль «Райский сад» для программы распада не содержит ни одной пары цепочек uf и gw.


4.2. Синтез

Рассмотрим программу, состоящую из одной команды вида



uk+qwusw.

Применимость. Эта программа применима ко всем ансамблям, содержащим пару слов вида uk и qw . FM(uk) > 0, FM(qw) > 0

Финитность. Очевидно, что программа всегда финитна. Она будет склеивать все пары соответствующих слов до тех пор, пока они не исчерпаются.

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

Критерий детерминированности синтеза

Программа синтеза детерминированна тогда и только тогда, когда выполняется хотя бы одно из условий:



  1. и

  2. и

  3. и

Доказательство.

1. Пусть в исходном ансамбле FM(uk)=n, FM(qw)=m, где u и w – некоторые фиксированные цепочки, и других слов вида uk и qw нет. Финальным ансамблем для данного ансамбля будет всегда следующий:

При nM'(usw)= FM(usw)+n, FM'(uk)=0, FM'(qw)=m–n.

При mM'(usw)= FM(usw)+m, FM'(uk)= n–m, FM'(qw)=0.

2. Пусть в исходном ансамбле

FM(uk)=n, FM(qw1)=m1, FM(qw2)=m2,… FM(qwl)=ml,

где u, w1, w2,…, wl – некоторые фиксированные цепочки, причем , и других слов вида uk и qw нет. Финальным ансамблем для данного ансамбля будет всегда следующий:



, FM'(qw1)=0, FM'(qw2)=0,…, FM'(qwl)=0,

FM'(usw1)=m1, FM'(usw2)=m2,…, FM'(uswl)=ml .

3. Пусть в исходном ансамбле



FM(qw)=m, FM(u1k)=n1, FM(u2k)=n2,…, FM(ulk)=nl,

где w, u1, u2,…, ul – некоторые фиксированные цепочки, причем , и других слов вида uk и qw нет. Финальным ансамблем для данного ансамбля будет всегда следующий:



, FM'(u1k)=0, FM'(u2k)=0,…, FM'(ulk)=0,

FM'(u1sw)=n1, FM'(u2sw)=n2,…, FM'(ulsw)=nl .

Видно, что условие 1 является частным случаем условия 2 или 3 в зависимости от того, что больше: n или m. Если эти условия не выполняются, то можно указать, по крайней мере, два различных ансамбля, которые будут финальны для данной программы и исходного ансамбля. Действительно, пусть исходным ансамблем будет следующий:



FM(uk)=n, FM(qw1)=m1, FM(qw2)=m2,…, FM(qwl)=ml,

где u, w1, w2,…, wl – некоторые фиксированные цепочки, но и других слов вида uk и qw нет, и пусть для определенности j=1…l . Укажем два возможных финальных ансамбля.



  1. FM'(uk)=0, , FM'(qw2)=0,…, FM'(qwl)=0, , FM'(usw2)=m2,…, FM'(uswl)=ml .

  2. FM'(uk)=0, FM'(qw1)=0, ,…, FM'(qwl)=0, FM'(usw1)=m1, ,…, FM'(uswl)=ml .

Недетерминированность в случае невыполнения условия 3 доказывается аналогично. Таким образом, критерий детерминированности для программы, состоящей из одной команды синтеза, доказан.

Пример недетерминированного синтеза

uK+QwuSw. FM(AK) =1, FM(QB)=1, FM(QA) = 1

В ансамбле M одно слово вида uK и два различных слова вида Qw, следовательно, этот ансамбль не удовлетворяет ни одному из условий критерия. Значит, синтез будет недетерминирован. Действительно, здесь есть два допустимых несовместных события. Финальными могут являться два различных ансамбля:



FM1(ASA) =1, FM1(QB)=1

и

FM2(ASB) =1, FM2(QA)=1.



Пример детерминированного синтеза.

uK+QwuSw. FM(AK) =3, FM(QB)=1, FM(QA) = 1

Данный ансамбль попадает под условие 2 критерия, следовательно, синтез будет детерминирован. Финальным будет ансамбль M1 такой, что



FM(AK) =1, FM(ASB)=1, FM(ASA) = 1

Ансамблями «Райский сад» для этой программы будут все такие ансамбли M, что для любого слова m такого, что FM(m) >0 .


4.3. Прямая замена

Рассмотрим программу, состоящую из одной команды вида uvw usw.



Применимость. Эта программа применима к ансамблю M, если существуют такие цепочки u, wL* , что FM(uvw) > 0 .

Финитность. Прямая замена не изменяет количества слов в ансамбле, она будет финитна если vs.

Детерминированность. Условия детерминированности прямой замены сходны с условиями детерминированности распада. Здесь также проверяется разложимость цепочки v на подцепочки вида aba и отслеживается вхождение цепочки вида ababa в слова исходного ансамбля или ансамбля, полученного применением программы прямой замены к исходному.
Критерий детерминированности прямой замены

Прямая замена не детерминирована, если существует разбиение цепочки v=aba и выполняется хотя бы одно из условий:

1. u,w такие, что FM(uababaw)>0;

2. s=xababay, где x, y – фикс. цепочки;

3. s=ds1, u1,w такие, что FM(u1cvw) > 0, где cd=ababa;

4. s=s1c, u,w1 такие, что FM(uv dw1) > 0 , где cd=ababa;

5. s=d, u1,w1 такие, что FM(u1c v ew1) > 0 , где cde=ababa;

В остальных случаях прямая замена детерминирована.




Каталог: Library
Library -> Аппендицит
Library -> Методические рекомендации для доаудиторной подготовки к практическим занятиям по инфекционным болезням
Library -> Нормы сроков службы стартерных свинцово-кислотных аккумуляторных батарей автотранспортных средств и автопогрузчиков
Library -> Что дает страхование ответственности перевозчика
Library -> Сообщения информационных агентств
Library -> Закон республики таджикистан о документах, удостоверяющих личность


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   32




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница