Синтез и отладка алгоритмов функционирования цифровых устройств управления. Вашкевич Н.П - 48 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

48
3.1 Автомат-распознаватель
Рассмотрим решение задачи, в которой требуется за один про-
смотр входной последовательности символов, заканчивающейся
специальным символом "
bottom
", идентифицировать наличие в ней
хотя бы одной из трёх искомых цепочек-образов. Входной алфавит
Z
=(
z
1
, ... ,
z
9
). Искомые цепочки-образы:
z
1
z
2
z
2
...
z
2
z
1
;
z
3
z
2
z
1
;
z
3
z
2
z
3
...
z
2
z
3
z
1
(многоточие означает появление символа, стоящего слева и
справа от него, любое число раз, но не менее одного). Необходимо
выполнить проектирование и исследование алгоритма работы ЦУ
для решения этой задачи.
При разработке алгоритма поиска совершенно не существенна
двоичная кодировка символов алфавита в реальной системе. Поэто-
му на данном этапе удобно работать с абстрактными входными сиг-
налами.
Для разработки алгоритма с использованием СОМПА рекоменду-
ется выполнить следующие шаги проектирования.
На первом шаге запишем алгоритм поиска цепочек в последова-
тельности символов регулярным выражением на языке РВАС (во-
просы идентификации цепочек-образов рассмотрены в [4]):
s
(
y
)=
s
0
(
z
1
z
2
{
z
2
}
z
1
∨
z
3
z
2
z
1
∨
z
3
{
z
2
z
3
}
z
1
).
На втором шаге в окне редактора РВАС введем это регулярное
выражение (рис. 3.1).
Рис. 3.1 
                  3.1 Автомат-распознаватель

   Рассмотрим решение задачи, в которой требуется за один про-
смотр входной последовательности символов, заканчивающейся
специальным символом "bottom", идентифицировать наличие в ней
хотя бы одной из трёх искомых цепочек-образов. Входной алфавит
Z=(z1, ... ,z9). Искомые цепочки-образы: z1z2z2 ... z2z1; z3z2z1; z3z2z3 ...
z2z3z1 (многоточие означает появление символа, стоящего слева и
справа от него, любое число раз, но не менее одного). Необходимо
выполнить проектирование и исследование алгоритма работы ЦУ
для решения этой задачи.

   При разработке алгоритма поиска совершенно не существенна
двоичная кодировка символов алфавита в реальной системе. Поэто-
му на данном этапе удобно работать с абстрактными входными сиг-
налами.
   Для разработки алгоритма с использованием СОМПА рекоменду-
ется выполнить следующие шаги проектирования.
   На первом шаге запишем алгоритм поиска цепочек в последова-
тельности символов регулярным выражением на языке РВАС (во-
просы идентификации цепочек-образов рассмотрены в [4]):
                     s(y)=s0(z1z2{z2}z1∨z3z2z1∨z3{z2z3}z1).
   На втором шаге в окне редактора РВАС введем это регулярное
выражение (рис. 3.1).




                                    Рис. 3.1




                                     48

Страницы