ВУЗ:
Составители:
42
2. Место, расположенное непосредственно справа от закрывающей (итераци-
онной или обыкновенной) скобки подчинено конечным местам всех термов много-
члена (в частном случае, одночлена), заключенного в соответствующие скобки, а в
случае итерационных скобок – также месту, расположенному непосредственно слева
от соответствующей открывающей скобки.
3. Начальные места всех термов многочлена (в частном случае, одночлена), за-
ключенного в итерационные скобки, подчинены месту, расположенному непосредст-
венно справа от соответствующей закрывающей скобки.
4. Место, расположенное непосредственно справа от символа пустого слова ε,
подчинено месту, расположенному непосредственно слева от этого символа.
5. Если место γ подчинено месту β, а место β подчинено месту α, то место γ
подчинено месту α (свойства транзитивности для отношения подчиненности мест).
6. Каждое место подчинено самому себе.
В качестве примера использования приведенной системы правил установим
отношение подчиненности мест для рассмотренного выше регулярного выраже-
ния (1). Место 1 кроме самого себя не подчинено никаким другим местам. То же са-
мое относится к местам 3, 5, 7, 9.
Места 2, 4 кроме самих себя, подчинены месту 1 (по правилу 1).
Место 6 и 8 – месту 5 (по правилу 1) и месту 10 (по правилу 3).
Место 10 подчинено (кроме самого себя) местам 5,7 и 9 (по правилу 2).
Место 11 подчинено (кроме самого себя) местам 3 и 10 (по правилу 2) и местам
5, 7 и 9 (по правилу 5).
Основными местами в таких выражениях считаются по определению все мес-
та, непосредственно слева от которых стоит буква основного алфавита, а также на-
чальное место.
Все места, непосредственно справа от которых стоит буква основного алфави-
та, называются предосновными.
Правила построения основного алгоритма синтеза конечных автоматов
1. Заданные регулярные события (число которых предполагается конечным)
представляются правильно записанными регулярными выражениями R
1
,…,R
p
. Все
места (как основные, так и не основные) в этих выражениях обозначаются вертикаль-
ными черточками (линиями).
2. Каждому основному месту в выражениях R
1
,…,R
p
приписывается в качестве
индекса неотрицательное целое число. При этом всем начальным местам приписыва-
ется один и тот же индекс (нуль). Что же касается остальных основных мест, то они
нумеруются в произвольном порядке натуральными числами 1, 2, …
Все введенные здесь индексы называются основными. Основные индексы под-
писываются под вертикальными чертами соответствующих им (основных) мест и
подчеркиваются снизу общей для каждого из выражений R
1
,…,R
p
горизонтальной
разделительной чертой.
3. Индекс (основной) каждого основного места α распространяется в качестве
неосновного индекса на все места (как основные, так и неосновные), подчиненные
месту α, но отличные от него самого.
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »
