ВУЗ:
Составители:
9
- на языке РВАС записывается алгоритм поиска любой цепочки, как и в предыдущей
задаче;
- по РВАС строится СКУ и СВФ;
- СКУ изменяется (корректируется) так, что событие возникающее при обнаружении
какой-либо цепочки устанавливается и остается при каждом следующем поступ-
лении входного символа (тактовом сигнале).
- поиск завершается успешно, если конъюнкция всех таких событий становится равной
1 (все цепочки найдены) и неуспешно если до этого поступит символ "bottom".
Используем тот же пример что и в задаче 1, только теперь все искомые цепочки долж-
ны присутствовать во входной последовательности.
СКУ:
s
0
=1; s
1
=s
2
&z
1
∨
s
1
&z
1
; s
2
=s
3
&z
2
; s
3
=s
0
&z
3
; s
k1
=s
1
&z
3
∨
s
k1
;
s
4
=s
5
&z
1
; s
5
=s
0
&z
2
∨
s
5
&z
2
;
s
k2
=s
4
&z
3
∨
s
k2
;
s
6
=s
7
&z
3
;
7
=s
8
&z
2
∨
s
7
&z
2
; s
8
=s
0
&z
4
∨
s
8
&z
4
;
s
k3
=s
6
&z
1
∨
s
k3
&z
1
∨
s
k3
;
s
b
=s
0
&bottom
∨
s
b
;
СВФ:
y=s
k1
&s
k2
&s
k3
; y
b
=s
b
.
Решение задачи типа "3". При разработке алгоритма решения этой задачи наряду с
замечаниями к задаче "2" нужно еще учесть, что нельзя заранее знать порядок , в котором
появятся цепочки во входной последовательности. Используем тот же пример что и в за-
даче 1, только теперь необходимо найти хотя бы две цепочки из трех.
При переходе от РВАС к СКУ и СВФ проделаем тоже, что и в задаче 2, но по иному
выполним коррекцию СВФ.
СКУ:
s
0
=1;
s
1
=s
2
&z
1
∨
s
1
&z
1
; s
2
=s
3
&z
2
; s
3
=s
0
&z
3
; s
k1
=s
1
&z
3
∨
s
k1
;
s
4
=s
5
&z
1
; s
5
=s
0
&z
2
∨
s
5
&z
2
;
s
k2
=s
4
&z
3
∨
s
k2
;
s
6
=s
7
&z
3
; s
7
=s
8
&z
2
∨
s
7
&z
2
; s
8
=s
0
&z
4
∨
s
8
&z
4
;
s
k3
=s
6
&z
1
∨
s
k3
&z
1
∨
s
k3
;
s
b
=s
0
&bottom
∨
s
b
;
СВФ:
y=s
k1
&s
k2
∨
s
k1
&s
k3
∨
s
k2
&s
k3
;
y
b
=s
b
.
Решение задачи типа "4". Рассмотрим решение такой задачи когда префикс будет за-
дан регулярным выражением z
1
z
1
z
2
z
3
, суффикс - z
2
{z
1
}z
3
, а корни будут из задачи 1. Не-
обходимо найти во входной последовательности любую цепочку из трех. Тогда алгоритм
поиска на языке РВАС запишется:
r(y)=s
0
z
1
z
1
z
2
z
3
(z
3
z
2
z
1
{z
1
}z
3
∨
z
2
{z
2
}z
1
z
3
∨
z
4
{z
4
}z
2
{z
2
}z
3
z
1
{z
1
})z
2
{z
1
}z
3
.
Разобьем выражение r на три части:
s
p
=s
0
z
1
z
1
z
2
z
3
- для префикса,
s
к1
=s
p
(z
3
z
2
z
1
{z
1
}z
3
) - для корня 1,
- на языке РВАС записывается алгоритм поиска любой цепочки, как и в предыдущей задаче; - по РВАС строится СКУ и СВФ; - СКУ изменяется (корректируется) так, что событие возникающее при обнаружении какой-либо цепочки устанавливается и остается при каждом следующем поступ- лении входного символа (тактовом сигнале). - поиск завершается успешно, если конъюнкция всех таких событий становится равной 1 (все цепочки найдены) и неуспешно если до этого поступит символ "bottom". Используем тот же пример что и в задаче 1, только теперь все искомые цепочки долж- ны присутствовать во входной последовательности. СКУ: s0=1; s1=s2&z1 ∨ s1&z1; s2=s3&z2 ; s3=s0&z3; sk1=s1&z3 ∨ sk1; s4=s5&z1; s5=s0&z2 ∨ s5&z2; sk2=s4&z3 ∨ sk2; s6=s7&z3; ∨ 7=s8&z2 s7&z2; s8=s0&z4 ∨ s8&z4; sk3=s6&z1 ∨ sk3&z1 ∨ sk3; sb=s0&bottom ∨ sb; СВФ: y=sk1&sk2&sk3; yb=sb. Решение задачи типа "3". При разработке алгоритма решения этой задачи наряду с замечаниями к задаче "2" нужно еще учесть, что нельзя заранее знать порядок , в котором появятся цепочки во входной последовательности. Используем тот же пример что и в за- даче 1, только теперь необходимо найти хотя бы две цепочки из трех. При переходе от РВАС к СКУ и СВФ проделаем тоже, что и в задаче 2, но по иному выполним коррекцию СВФ. СКУ: s0=1; s1=s2&z1 ∨ s1&z1; s2=s3&z2; s3=s0&z3; sk1=s1&z3 ∨ sk1; s4=s5&z1; ∨ s5=s0&z2 s5&z2; sk2=s4&z3 ∨ sk2; s6=s7&z3; s7=s8&z2 ∨ s7&z2; s8=s0&z4 ∨ s8&z4; ∨ ∨ sk3=s6&z1 sk3&z1 sk3; sb=s0&bottom ∨ sb; СВФ: y=sk1&sk2 ∨ sk1&sk3 ∨ sk2&sk3; yb=sb. Решение задачи типа "4". Рассмотрим решение такой задачи когда префикс будет за- дан регулярным выражением z1z1z2z3, суффикс - z2{z1}z3, а корни будут из задачи 1. Не- обходимо найти во входной последовательности любую цепочку из трех. Тогда алгоритм поиска на языке РВАС запишется: r(y)=s0z1z1z2z3(z3z2z1{z1}z3 ∨ z2{z2}z1z3 ∨ z4{z4}z2{z2}z3z1{z1})z2{z1}z3. Разобьем выражение r на три части: sp=s0z1z1z2z3- для префикса, sк1=sp(z3z2z1{z1}z3) - для корня 1, 9
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »