Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 202 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

202
S
5
=S
0
z
2
S
5
z
2
S
k2
=S
4
z
3
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
СВФ:
y=S
k1
S
k2
S
k3
Для поиска цепочек в любом месте последовательности необходимо
устанавливать маркер начала поиска перед приемом каждого следующего
символа. Поэтому в СКУ нужно добавить уравнение: S
0
=1, а чтобы учесть
поступление символа z
b
необходимо добавить еще одно уравнение в СКУ и
одно в СВФ:
СКУ:
S
0
=1
S
b
=S
0
z
b
S
b
;
СВФ:
y
b
=S
b
.
При практической реализации алгоритма необязательно повторять
переходы из S
b
в S
b
. Для программной реализации достаточно будет
остановить выполнение программы, а при аппаратной реализации
блокировать прохождение синхросигнала на элементы памяти.
Решение задачи типа "2". Получить алгоритм решения этой задачи
возможно следующим образом:
- на языке РВАС записывается алгоритм поиска любой цепочки, как и в
предыдущей задаче;
- по РВАС строится СКУ и СВФ;
- СКУ изменяется (корректируется) так, что событие, возникающее при
обнаружении какой-либо цепочки, становится равным 1 и остается таким при
каждом последующем поступлении входного символа (тактовом сигнале).
- поиск завершается успешно, если конъюнкция всех таких событий
становится равной 1 (все цепочки найдены) и неуспешно, если до этого
поступит символ z
b
.
Используем тот же пример что и в задаче 1, только теперь все искомые
цепочки должны присутствовать во входной последовательности.
СКУ:
S
0
=1
S
1
=S
2
z
1
S
1
z
1 
     S5=S0z2  S5z2
     Sk2=S4z3
     S6=S7z3
     S7=S8z2  S7z2
     S8=S0z4  S8z4
     Sk3=S6z1  Sk3z1
     СВФ:
     y=Sk1  Sk2  Sk3
      Для поиска цепочек в любом месте последовательности необходимо
устанавливать маркер начала поиска перед приемом каждого следующего
символа. Поэтому в СКУ нужно добавить уравнение: S0=1, а чтобы учесть
поступление символа zb необходимо добавить еще одно уравнение в СКУ и
одно в СВФ:
      СКУ:
      S0=1
      Sb=S0zb  Sb;
      СВФ:
      yb=Sb.
      При практической реализации алгоритма необязательно повторять
переходы из Sb в Sb. Для программной реализации достаточно будет
остановить выполнение программы, а при аппаратной реализации
блокировать прохождение синхросигнала на элементы памяти.
      Решение задачи типа "2". Получить алгоритм решения этой задачи
возможно следующим образом:
      - на языке РВАС записывается алгоритм поиска любой цепочки, как и в
предыдущей задаче;
      - по РВАС строится СКУ и СВФ;
      - СКУ изменяется (корректируется) так, что событие, возникающее при
обнаружении какой-либо цепочки, становится равным 1 и остается таким при
каждом последующем поступлении входного символа (тактовом сигнале).
      - поиск завершается успешно, если конъюнкция всех таких событий
становится равной 1 (все цепочки найдены) и неуспешно, если до этого
поступит символ zb.
      Используем тот же пример что и в задаче 1, только теперь все искомые
цепочки должны присутствовать во входной последовательности.
      СКУ:
      S0=1
      S1=S2z1  S1z1

                                                                       202

Страницы