ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 113
Скачиваний: 0
дит только одна стрелка, отмечаем символами 1 |
s. В ГСА на рис. 4-7 |
s = 9.
2.Записываем оператор Ун, соответствующий начальной вершине ГСА.
3.Если вход вершины, следующий за начальной, отмечен символом / в п. 1,
то после оператора У„ ставим нижнюю стрелку ф. В рассматриваемом примере
этого нет.
4. Если за начальной вершиной ГСА следует операторная вершина, в ко торой записан оператор Y(, то справа к У„ приписываем У/. Если же за началь ной вершиной следует условная вершина, в которой записано логическое усло-
Рис. 4-7. Иллюстрация перехода от ГСА к ЛСА
вне хт, то справа к Уп приписываем хт. Справа от хт ставим верхнюю стрелку, над которой записываем і, если вход вершины, следующей за рассматриваемой условной вершиной по выходу «О», отмечен меткой і. Если такой метки нет, то
справа от хт ставим просто верхнюю стрелку. В нашем примере имеем: Упх1'|'. 5. Если в п. 4 рассматривалась операторная вершина и вход следующей
за ней вершины отмечен в п. 1 символом р, то вслед за У; ставим нижнюю стрелку
р
ф, после которой записываем содержимое вершины, следующей за операторной вершиной с оператором У/. Если в п. 4 рассматривалась условная вершина с ло
гическим условием хт, то после ее верхней стрелки записываем нижнюю стрелку
р
ф, если вход вершины, следующей за этой условной вершиной по выходу «1», отмечен символом р. В противном случае нижняя стрелка не ставится. После этого справа к xmf приписываем содержимое вершины, следующей за рассмат риваемой условной вершиной по выходу «1». В нашем примере имеем:
УпХі і Уѵ
6. Продолжаем аналогичным образом до тех пор, пока:
63
s
а) после некоторого оператора Y ( не окажется нижняя стрелка ф, где s — от метка конечной вершимы. Тогда после У; ставится ложное логическое условие
S
со с верхней стрелкой s: . . . У^шф;
ч
б) после некоторого оператора Y t не окажется нижняя стрелка ф, такая, что
<1
слева от нее на каком-либо месте в этой строчке уже есть инжияя стрелка ф.
<?
Тогда нижняя стрелка ф после Yt убирается, а вместо нее ставится тождественно
|
|
<7 |
<7 |
ложное логическое условие со с верхней стрелкой f(cof); |
|||
в) |
в этой строчке после некоторого логического условия хт со своей верх- |
||
ней стрелкой |
S |
|
|
не окажется нижняя стрелка ф, где s — отметка конечной вер |
|||
шины. |
Тогда |
после л-,,,! ставится тождественно ложное логическое условие со |
|
с верхней стрелкой s: |
|
||
|
|
f ^ [ I |
|
г) |
в этой строчке после некоторого логического условия хт со своей верх- |
||
|
|
17 |
|
ней стрелкой (хт^) не окажется нижняя стрелка ф (это означает, что в ГСА за ус ловной вершиной, в которой записано это хт, по выходу «1» следует вершина,
вход которой отмечен символом q), |
а слева от хт в этой строчке уже есть ннж- |
17 |
<7 |
няя стрелка ф. Тогда нижняя стрелка ф после хт^ убирается, а вместо нее запи-
'7
сывается тождественно ложное условие со с верхней стрелкой фч
<7
• ■ ■хт f со j .
В нашем примере написание первой строчки закончилось после того, как
1
вслед за У7 оказалась нижняя стрелка ф, для которой ранее уже была нижняя стрелка (см. условие «б»):
1 |
8 4 |
2 |
5 6 |
8 |
1 |
УНЛ'і І УI |
! А'з [ Х2 \ X-J J |
|
ф YЗ.ѵ8 I |
фХх і IУ7 ф. |
|
. После записи іо вслед за У7 с верхней стрелкой f получим:
|
1 |
8 4 2 5 |
6 8 |
1 |
•(4- |
|
УіЛ I Уі J |
хз t Х2Ii J Уз-'s t |
J -'-Tt |
ФУ710 I |
|
7. |
Над первой слева верхней стрелкой без цифры в ЛСА (4-4) |
записываем |
|||
число s + 1 , где s — наибольший |
номер отметки |
в п. 1 : |
|
||
|
|
ю |
|
|
|
|
Унл'і і Уі • • • |
s+ 1 |
|
|
|
8. |
|
|
вслед за которой запи |
||
Начинаем новую строчку с нижней стрелки ф , |
|||||
сываем содержимое вершины, следующей по выходу «О» за условной вершиной
с логическим условием х г (над стрелкой после х х мы записали s + |
1 = 10): |
|||||||
|
|
|
|
10 |
|
|
|
|
9. Продолжаем далее, так же как при построении первой строчки, с той |
||||||||
лишь разницей, что условия п. |
6 проверяются по всем построенным ранее строч |
|||||||
кам., В результате получим шесть строчек: |
|
|
|
|
||||
10 |
І_ |
11 |
12 |
8 4 |
2 5 |
6 8 |
1 |
|
УнА-'і t |
У Л -Kst |
*Л |
*7 Т j |
УЗ.ѵ8н |
*1 f фУ7со f , |
(4-5) |
||
64
10 |
13 |
'3 |
1 |
i |
-v-Gt |
-v2t |
Y 2co f > |
|
11 |
2 |
‘1 |
|
|
1 х2f со f , |
|
||
12 |
86 |
14 |
9 |
|
1 У0.V0t U-7 t |
У0ш t . |
|||
13 |
6 3 |
5 |
|
|
1 |
ПУ., cot, |
|
||
|
14 |
CO |
9 |
|
|
>— |
—Ч |
|
|
|
|
3 |
|
|
(4-6)
(4-7)
(4-8)
(4-9)
(4-10)
Первая, вторая и пятая строчки обрываются после выполнения условия 66,
третья — условия 6г, а четвертая |
и шестая — 6а. |
10. После выполнения п. 9 оказалось, что больше нет иенадписанных верх |
|
них стрелок. Находим такое г (I к |
г < s, где s — число отметок на ГСА в п. 1), |
|
г |
что в построенных строчках пет нижней стрелки ф. После этого строим новую
г
строчку, начинающуюся со стрелки ф, вслед за которой записано содержимое вер шины, отмеченной символом г. В нашем примере г = 2 и 7:
2 з
1 х.і f щ I .
11. Продолжая далее как и выше, получаем еще две строчки:
|
2 |
15 |
з |
|
|
|
|
U „ t |
cot, |
|
|
(4-П) |
|
15 |
5 |
7 |
7 |
8 |
5 |
|
Л -Л П Л о U 3 U 4t y u m t. |
(4-12) |
|||||
|
|
|
|
|
|
s |
12. Последняя строчка для любой граф-схемы состоит из нижней стрелки где s — отметка конечной вершины, и символа конечного оператора. В нашем примере:
|
|
|
|
|
|
|
|
I |
Ук- |
|
|
|
|
|
|
(4-13) |
|
|
13. Строчки (4-5) |
— (4-13) записываем |
|
в одну строчку |
таким |
образом,что |
|||||||||||
вначале стоит |
|
первая |
строчка |
(4-5), в конце — последняя |
(4-13), аостальные |
||||||||||||
располагаются в произвольном порядке1: |
|
|
|
|
|
|
|
|
|||||||||
|
10 |
1 |
11 |
12 |
|
8 4 |
|
2 5 |
6 8 |
1 |
10 |
13 |
3 |
1 |
|
|
|
Ун*1 t |
УЛ Х 3 t |
*2 f |
*7 N |
У3*8 f U |
l t |
I У7“ |
f I *G f |
*2 t УоМ t |
|
|
|||||||
|
|
|
|
11 |
|
2 |
. 4 12 |
8 6 14 |
|
|
9 13 |
G3 |
5 14 |
9 2 15 |
3 |
||
|
|
|
|
i |
X21 Ш11 |
У0*6 f U 71 y 9co f I |
t I У4С0 tI |
y 8w f |
U 41 |
COt |
|||||||
15 |
5 |
7 |
|
7 |
8 |
|
5 9 |
|
|
|
|
|
|
|
|
|
|
i |
*5 t Ув^іо I *at xi t УцСО f 1 Ук- |
|
|
|
|
|
|
|
(4-14) |
||||||||
Из самого способа построения ЛСА видно, что она равносильна ГСА па рис. 4-7. Нетрудно также показать, что число операторов и логических условий (без тождественно ложных) в построенной таким образом ЛСА совпадает соот ветственно с числом операторных и условных вершин в исходной граф-схеме.
Алгоритм перехода от ЛСА к ГСА..очевиден. Соответствующая ГСА имеет одну начальную и 1 конечную вершины, число ее операторных вершин равно
1 Окончательная ЛСА занимает три строчки лишь потому, что она не поме стилась в одну строчку.
65
числу операторов в ЛСА, а число условных вершин — числу логических усло вии в ЛСА (без учета тождественно ложных). Выход начальной вершины ГСА соединяется дугой со входом вершины, соответствующей в ЛСА ближайшему справа от У„ оператору или логическому условию. Аналогично в граф-схеме проводятся дуги из операторных вершин. Единичный выход из условной вер шины в ГСА, соответствующей в ЛСА логическому условию хт< соединяется со входом вершины, соответствующей ближайшему справа от хт оператору или логическому условию. Если после логического условия хт в ЛСА стоит-верхняя
стрелка ф, то нулевой выход условной вершины, соответствующей хт, соеди няется со входом вершины, соответствующей оператору или логическому усло
вию, перед которыми стоит нижняя стрелка ф. Если после оператора Y t в ЛСА
стоит тождественно ложное логическое условие (о с верхней стрелкой і (шф), то выход операторной вершины, соответствующей Yt, соединяется со входом вершины, которая соответствует оператору или логическому условию, стоящему
после нижней стрелки ф. Точно так же если после логического условия хт со
своей стрелкой (д'т ф) стоит соф, то единичный выход условной вершины, соот ветствующей хт, соединяется со входом вершины, которая соответствует опера
тору пли логическому условию, стоящему после нижней стрелки ф.
Если от ЛСА (4-14) перейти к ГСА, то получим граф-схему на рис. 4-7.
4-5. Формулы перехода |
|
|
|
|
Тот факт, что от любого оператора Y t |
возможен переход к некото |
|||
рым операторам из множества (У), |
. . . , |
У., . . . , Уг+1], молено опи |
||
сать с помощью выражения: |
|
|
|
|
где а,у — функция |
перехода от У,- |
к У;- — булева функция перемен |
||
ных х х, . . . , xL; |
aijYj — отмеченная булева функция. |
|||
Отмеченная функция |
|
|
|
|
|
'Yj, |
если |
ос,у= 1; |
|
|
0, |
если |
а,у = 0. |
|
Над логическими функциями, входящими в отмеченные функции, можно производить все преобразования алгебры логики. В работе [20] определены правила, которые совместно с полной системой ак сиом алгебры логики образуют систему правил тождественного преоб разования отмеченных функций:
1. ( a V ß J ^ o r t W ß ^ .
2. а &Y№ ¥ , = <* фУЫуУ,).
3. |
Если а = ß (а эквивалентно ß), то а У, = ßy,-. В этих выраже |
ниях а, ß и у — булевы функции переменных х х, . . . , xL. |
|
Формулы вида (4-15) носят названия формул перехода для опера |
|
тора |
YI. Множество формул перехода для всех і — 0, 1...........Т об- |
66
разует систему формул перехода. Для ГСА на рис. 4-5 эта система имеет вид:
Y о —> |
XjY i ', |
|
|
Y 1-> Уа; |
|
|
|
Y 2—>x2 Y 3 |
\Jx3 Y 4, |
|
|
Y 3 -> x2 Y аХ/х^ХдУg\/x2 XsYg', |
|||
Y .1—►XnY0 \JX'2 X3 Yg\JX0 X3 |
Y 5“, |
||
Y 6 |
-> У«; |
|
1 |
Y c -> x4 Y K\ f x4 Y 7; |
|
||
Y |
x 2 Y 3\ f x2 Y 4\ |
|
|
Ys -> ^ k- |
|
|
|
Представление формулы перехода в виде |
|
||
Y { -> X iA \Jx ß , |
(4-16) |
||
где X[ £ (xj, . . . , *L], а А и В — подформулы перехода, не завися щие от xh носит название приведения формулы перехода по перемен ной Х[. Приведем формулу перехода для оператора Y 3 по переменной
Хо•
Y з -> x2 Y в\ / x2 (x3 Y S\Jx3 Y 5). |
(4-17) |
Если какие-то члены формулы перехода не зависят от *,, то при приведении по xt необходимо предварительно умножить их на выра
жение (хі |
V xt). Так, приведение формулы перехода для Y 3 по пере |
менной х3 |
имеет вид: |
Y з -> Хо (*зѴ*з) Y 3 \ / x2 x3Y 3\Jx2 x^Y5=
— х3 (x2Y 6\/ xYY%)\JX3(л:2Y е\Jx2Y 5). (4-18)
В формуле (4-16) можно продолжать приведение подформул А и В по другим переменным, до тех пор пока во внутренних скобках не окажутся выражения вида
(xpY n\JxpY k),
(4-19)
х р £ {Л:і* • • • > x l }> Y п , Y k ^ \ Y ѵ . . . , У г + 1 ).
Такая форма записи формулы перехода называется скобочной фор
мой, система таких формул — системой скобочных формул |
перехода |
[8 ]. Выражения вида (4-19) носят названия элементарных |
выраже |
ний. |
|
Покажем на более сложном примере процесс приведения к скобоч ной форме. Формула перехода
Yt-> *1*2*4Y4V *1*2*3 ^ 4V хгх2х3хйY4V ХіА-оХ.1У 4 оV
V * 1 * 2 * 4 ^ 4 V * l * 2 * 3 * 5 ^ 7 \ / * 1 * 2 * 4 ^ 9 V * l* 2 * 4 'l ''9
67