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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

204
Решение задачи типа "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,
S
к2
=S
p
(z
2
{z
2
}z
1
z
3
) - для корня 2
S
к3
=S
p
(z
4
{z
4
}z
2
{z
2
}z
3
z
1
{z
1
}) - для корня 3
r(y)= S
r
z
2
{z
1
}z
3
- для суффикса.
Для каждого уравнения перейдем от РВАС к СКУ и объединим их. Получим:
СКУ:
S
0
=1
Для префикса (маркер начала поиска S
0
):
S
p
=S
9
z
3
S
9
=S
10
z
2
S
10
=S
11
z
1
S
11
=S
0
z
1
Для корней (маркер начала поиска S
p
):
S
1
=S
2
z
1
S
1
z
1
S
2
=S
3
z
2
S
3
=S
p
z
3
S
k1
=S
1
z
3
S
4
=S
5
z
1
S
5
=S
p
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
p
z
4
S
8
z
4
S
k3
=S
6
z
1
S
k3
z
1
Для суффикса (маркеры начала поиска S
k1
, S
k2
, S
k3
):
r=S
12
z
3
S
12
=(S
k1
S
k2
S
k3
)z
2
S
12
z
1
Для входного символа "bottom":
S
b
=S
0
z
b
S
b
;
СВФ:
y=r 
     Решение задачи типа "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,
     Sк2=Sp(z2{z2}z1z3) - для корня 2
     Sк3=Sp(z4{z4}z2{z2}z3z1{z1}) - для корня 3
     r(y)= Srz2{z1}z3 - для суффикса.
      Для каждого уравнения перейдем от РВАС к СКУ и объединим их. Получим:
      СКУ:
      S0=1
      Для префикса (маркер начала поиска S0):
      Sp=S9z3
      S9=S10z2
      S10=S11z1
      S11=S0z1
      Для корней (маркер начала поиска Sp):
      S1=S2z1  S1z1
      S2=S3z2
      S3=Spz3
      Sk1=S1z3
      S4=S5z1
      S5=Spz2  S5z2
      Sk2=S4z3
      S6=S7z3
      S7=S8z2  S7z2
      S8=Spz4  S8z4
      Sk3=S6z1  Sk3z1
      Для суффикса (маркеры начала поиска Sk1, Sk2, Sk3):
      r=S12z3
      S12=(Sk1  Sk2  Sk3)z2  S12z1
      Для входного символа "bottom":
      Sb=S0zb  Sb;
      СВФ:
      y=r

                                                                              204

Страницы