Выхованец В.С. Теория автоматов
Подождите немного. Документ загружается.
37
3
t
2
0
- -
0
1
4
t
-
0
1
-
1
0
5
t
- -
0
3
1
0
Начальная маркировка
()
0,1,0,2=M .
Число сетей Петри счетно.
ФОРМАЛИЗАЦИЯ ФУНКЦИОНИРОВАНИЯ СЕТЕЙ ПЕТРИ
Формализация функционирования сетей Петри заключается в последовательной смене
ее маркировок.
Пусть задана сеть Петри
METPS ,,,= , где nP = , mT = , с начальной маркировкой
{}
n
M
μμ
,...,
1
= , где n - число позиций, тогда функционирование сети Петри представляется как
последовательность смены маркировок
() () ()
......
10
→→→→
l
MMM .
Сеть Петри останавливается, если эта последовательность конечна и не останавливается в
противном случае.
Определение. Маркировка
M
называется ТУПИКОВОЙ, если является последней
маркировкой в конечной последовательности срабатывания.
Функционирование сети Петри опишем рекурсивными уравнениями.
()
1+K
M
есть некая функция
δ
от маркировки, зависящей от маркировки на предыдущем
шаге функционирования и
()
K
T
- возбужденные переходы на к-ом шаге, то есть
() ()()
()
() ()
()
⎪
⎩
⎪
⎨
⎧
−=
−=
+
.,
,,,
1
преходовявозбужденифункцияMT
маркировоксменыфункцияTMM
KK
KKK
ωω
δδ
Функция
δ
может быть случайной, так как должна выбрать из всех возбужденных
переходов только один.
Функция
ω
детерминированная, то есть четко определенная.
Рассмотрим первое уравнение и два вектора:
()
iniii
ππππ
,...,,
21
= - вектор возбуждения переходов,
()
iniii
ττττ
,...,
21
= - вектор срабатывания переходов.
()
(
)
()
⎪
⎩
⎪
⎨
⎧
−
=
.
,,0
ijji
ijji
ijij
PвотвPотведущейдугикратностьn
PвотвдугинетPотесли
ττ
ττ
τπ
Заметим, что в таблице инцидентности находятся числа
ij
ij
τ
π
.
Дадим содержательную интерпретацию векторов
τ
π
, .
Вектор
i
π
определяет на сколько уменьшится маркировка сети Петри при срабатывании
i -ого перехода.
Вектор
i
τ
определяет насколько изменится маркировка сети Петри при срабатывании i -
ого перехода.
Откуда находим
() ()
ii
KK
MM
πτ
−+=
+1
, где
i
π
- числитель i - ой строки,
i
τ
- знаменатель i - ой строки.
() ()
i
KK
ФMM +=
+1
, где
i
Ф - вектор разностей
ii
πτ
− .
38
Рассмотрим уравнение
() ()
i
KK
ФMM +=
+1
. Оно задает вектор возбуждаемых переходов на
k - ом шаге функционирования сети Петри
() () () ()
()
,,...,,
21
K
m
KKK
T ΕΕΕ= , где
()
⎪
⎩
⎪
⎨
⎧
=Ε
.,1
,,0
возбужденпереходtесли
возбужденнепереходtесли
i
i
K
i
Определение. Для определения функции возбуждения переходов необходимо ввести
отношения сравнения векторов – целых чисел длинной n . Если заданы
две маркировки
()
u
M
и
()
v
M
, то будем говорить, что маркировка
() ()
vu
M
M
≥ , если для всех
() ()
()
niMM
v
i
u
i
,...,1, =≥ (производится
покомпонентное сравнение векторов
()
u
M
и
()
v
M
).
Дадим содержательную интерпретацию отношения ≥ . Если покомпонентно вектор
()
u
M
больше вектора
()
v
M
, то выполняется соотношение ≥ .
Пример.
()()
1,1,02,1,0 ≥
Аналогично выводятся соотношения >≠=≤< ,,,,.
Условием возбуждения переходов является
()
()
(
)
ni
ii
K
i
K
,...,1, =≥=Ε
πμ
()
() () ()
(
)
nni
K
KKK
T
πμπμπμ
≥≥≥= ,...,,
221
, то есть число меток в каждой позиции должно
быть больше или равно кратности дуг ведущих из данной позиции в переход
i
t . Для
вычисления вектора
()
K
T
необходимо сравнить покомпонентно текущую маркировку с
числителями строк таблицы инцидентности.
Таким образом осталась не определена функция смены маркировок
δ
, которая случайно
или по какому-то закону выбирает из возбужденных переходов срабатываемый.
Пример. Пусть задана сеть Петри двудольным графом и таблицей инцидентности.
PT \
1
P
2
P
3
P
1
t
1
1
1
0
-
2
t
0
1
0
2
1
0
3
t
1
0
-
0
1
4
t
-
2
0
0
1
Вычислим вектора
i
Ф .
39
()
()
()
()
.1,2,0
,1,0,1
,1,2,1
,0,1,0
4
3
2
1
−=
−=
−−=
=
Ф
Ф
Ф
Ф
Вычислим вектор возбуждения переходов
T
. Рассмотрим начальную
маркировку
()
()
0,2,1
0
=M . Проверяем условие возбуждения переходов. Так как
условие возбуждения переходов выполняется, то вектор возбуждения переходов
будет
()
()
0,0,2,1
0
=T . Предположим сработал второй переход, тогда получим
вектор маркировок
()
()( )()
1,0,01,2,10,2,1
1
=−−+=M ,тогда
()
()
1,1,0,0
1
=T и так далее.
Определение.
Маркировка
()
l
M
ДОСТИЖИМА из маркировки
()
K
M
если существует
последовательность маркировок сети Петри, оканчивающаяся
маркировкой
()
l
M
, где
()
()
()
() ()
()
lttKtK
MMM
lKK
⎯⎯→⎯⎯⎯→⎯⎯→⎯
−+
+
11
...
1
() ()
lQK
MM ⎯→⎯ , где
()( ) ( )
11
...
−+
=
lKK
tttQ - строка в алфавите переходов
*
TQ ∈ . То есть при функционировании сети Петри порождается строка в
алфавите переходов.
Определение.
МНОЖЕСТВО ДОСТИЖИМЫХ МАРКИРОВОК
R
для сети Петри S
из маркировки
()
K
M
есть всевозможные маркировки
()
l
M
такие, что из
маркировки
()
K
M
достижима маркировка
()
l
M
при конечном числе
срабатываний переходов.
()
()
() ( )
{
}
*
;|, TQMMMMSR
l
Q
KlK
∈⎯→⎯=
Если маркировка
()
M
M
K
= - начальной маркировке сети Петри, то
множество достижимых маркировок
()()
SRMSR =, называется
МНОЖЕСТВОМ ДОСТИЖИМЫХ МАРКИРОВОК СЕТИ ПЕТРИ.
Определение.
СВОБОДНЫЙ ЯЗЫК СЕТИ ПЕТРИ
()
SL есть множество конечных
последовательностей срабатывания сети Петри
S
()
()
()
{
}
SRMMTQSL
l
Q
⊂⎯→⎯∈= |
*
, то есть таких, что из начальной
маркировки
M
получается достижимая маркировка
()
l
M
сети Петри S .
СВОБОДНЫЙ ЯЗАК СЕТИ ПЕТРИ
()
SL - это множество строк в
алфавите
T
ведущих от начальной маркировки сети к каждой
допустимой (достижимой) маркировке
()
l
M
сети Петри S .
Множество свободных языков, порождаемых всевозможными сетями Петри, образуют
класс свободных языков
s
L .
Определение.
ПОМЕЧЕННАЯ СЕТЬ ПЕТРИ есть совокупность трех объектов
()
λ
,, ASS =
)
, где
{}
METPS ,,,= - сеть Петри,
{}
K
aaaA ,...,,
21
= - помечающий алфавит,
AT →:
λ
- помечающая функция (отображение), ставящее в соответствие
каждому переходу знак алфавита
A .
Пример. Пометим сеть Петри следующего вида
40
Зададим алфавит
{}
cbaA ,,= . Помечающую функцию
λ
представим в
следующем виде
Тогда помеченная сеть Петри будет иметь вид:
Определение.
ПРЕФИКСНЫЙ ЯЗЫК ПОМЕЧЕННОЙ СЕТИ ПЕТРИ S
)
Есть
всевозможные строки в алфавите
A такие, что
()
() (){}
SLQQSL ∈= |
λ
)
Это есть множество значащих строк, принадлежащих языку
()
SL в
помечающем алфавите
A , соответствующих одной из возможных
последовательностей срабатывания сети Петри
S , задаваемая
помечающей функцией
λ
.
Определение.
ТЕРМИНАЛЬНЫЙ ЯЗЫК ПОМЕЧЕННОЙ СЕТИ ПЕТРИ S
)
.Удобно
рассматривать не свободный язык сети Петри
()
SL
)
, а его подмножество
терминальных сток, ведущих от начальной маркировки
()
0
M
к некоторой
41
фиксированной маркировки
()
f
M
.
() ( )
fS
MM ⎯→⎯
)
0
.
То есть терминальный язык
()
SL
)
есть всевозможные строки в алфавите A
такие, что помечающая последовательность
Q переводит начальную
маркировку сети Петри
()
0
M
в заданную маркировку
()
f
M
.
()
()
()
() ( )
{}
f
Q
f
MMAQMSL ⎯→⎯∈=
0*
|,
λ
)
.
Пример.
Пусть задана сеть Петри
()
λ
,, ASS =
)
двудольным графом
Введем помечающий алфавит
{}
baA ,= и пометим данную сеть Петри.
Эта сеть Петри порождаюет свободный язык сети Петри
()
SL , строками
которого являются следующие последовательности срабатывания
переходов
,...
,
,
43211
433211
4321
ttttt
tttttt
tttt
Префиксный язык сети Петри
()
{}
,...,,
233322
bababaSL =
)
.
Терминальный язык сети Петри
()
()
{}
,...,,0,0,0,1,
233322
bababaSL =
)
.
В общем случае эта сеть Петри порождает следующий терминальный
язык
()
()
{}
{}
0\|0,0,0,1, /∈= NnbaSL
nn
)
.
ТЕОРЕМА 2.5. О мощности классов языков сети Петри.
Введем следующие обозначения.
Пусть
S
L - языки, которые могут быть порождены всевозможными сетями Петри.
Пусть
П
L - всевозможные префиксные языки, порождаемые всевозможными сетями
Петри.
Пусть
T
L - терминальные языки, соответствующие всевозможным маркировкам
всевозможных сетей Петри.
{ }{} {}{}
,......,...,...,,...,
21
ttL
S
= - счетно. Тогда мощность класса терминальных языков сетей
Петри превосходит мощность классов префиксных языков, причем
TП
LL ⊂ .
ДОКАЗАТЕЛЬСТВО.
Класс префиксных языков
П
L порождается всевозможными последова-тельностями
срабатывания всевозможных сетей Петри, причем только тех последовательностей,
которые заканчиваются тупиковой маркировкой. Понятно, что класс терминальных
языков более мощен, чем класс префиксных языков и включает часть его, так как помимо
последовательностей срабатывания, приводящих к тупиковым маркировкам, содержит и
последовательности срабатываний, приводящих к всевозможным заключительным
маркировкам
()
f
M
, в том числе и к тупиковым.
Окончание доказательства.
42
ТЕОРЕМА 2.6. О мощности классов языков сетей Петри, по отношению к классам
языков, порождаемых формальными грамматиками.
Класс терминальных языков сетей Петри:
1. Строго мощнее, чем класс языков, порождаемых регулярными грамматиками
T
LL ⊂
3
.
2. Не сравним с классом языков, порождаемых КС грамматиками
T
LL ≠
2
.
3. Менее мощен, чем класс языков, порождаемых произвольными грамматиками
0
LL
T
⊂ .
Таким образом
023
LLLL
T
⊂≠⊂ .
ДОКАЗАТЕЛЬСТВО.
A. Докажем, что
T
LL ⊂
3
.
Произвольный регулярный язык
3
L может быть представлен помеченной сетью
Петри S
)
, порождающей тот же язык в качестве терминального.
Если задана помеченная сеть Петри
λ
,,,,, AMETPS =
)
и регулярная
грамматика
PIWVG ,,,
3
= , то каждому нетерминальному знаку WA∈ поставим в
соответствие позиции PP
A
∈ .
PPWA
A
∈↔∈∀ .
Каждой продукции вида
VaWABaBA ∈∈→ ,; поставим в соответствие дугу с
переходом, помеченным знаком a , идущую от позиции
A
P к позиции
B
P .
В качестве заключительной маркировки
()
f
M
выберем маркировку, где первая
позиция соответствует заключительной сентенциальной форме, когда удается
единственный нетерминальный знак продукций вида
aA → .
()
()
43421
1
0,...,0,0,0,1
+
=
W
f
M .
Начальная маркировка
M
такова, что число меток в позиции
I
P равно 1.
()
,...1,..,0=M , 1=
I
M в позиции
I
P .
Пример. Пусть задана регулярная грамматика
IPWVG ,,,=
{}
baV ,= ,
{}
BAIW ,,= ,
⎪
⎩
⎪
⎨
⎧
→
→
→
=
.|
,|
,||
bAbB
aBaA
bAaBaI
P
Построим сеть Петри, порождающую тот же язык, что и регулярная грамматика
G
()
()
GLSL =
)
.
43
Где
0
P - заключительная или нулевая позиция.
Заключительной маркировкой будет маркировка
()
()
0,0,0,1=
f
M . Очевидно, что сеть
Петри порождает то же язык, что и регулярная грамматика
G .
Однако существуют сети Петри, которые порождают языки, не
являющийся регулярными.
Пример. Пусть есть следующая сеть Петри
Данная сеть Петри порождает строки следующего вида
[][][[]],[], -
правильно расставленные скобки. Тогда грамматика
порождающая этот язык будет
PIWVG ,,,=
{}
][,=V ,
{}
IW = ,
{}
[]||][ IIIIP →= .
Очевидно, что грамматика
G - КС грамматика. Язык
()
GL невозможно
породить регулярной грамматикой.
B. Докажем, что
T
L не сравним с
2
L , то есть
2
LL
T
≠ . То есть не все КС языки могут
быть представлены сетями Петри, а так же есть языки, представимые сетями Петри, но
которые не могут быть порождены КС грамматиками.
Пример. Приведем пример не КС языка, порождаемого сетью Петри.
Рассмотрим язык
()
()
NncbaGL
nnn
∈= |. Ранее доказывалось, что этот
язык порождается контекстной грамматикой (см глава 1).
Однако существует КС язык, на порождаемый сетью Петри.
Пример. Рассмотрим следующую грамматику
PIWVG ,,,= с продукциями
вида
{}
eaAbAAAAcIP ||, →→= . Очевидно, что данная грамматика
порождает строки вида
cba
nn
.
C. Таким образом получаем:
44
, где КА – конечный автомат,
МА – магазинный автомат,
2-Х МА – двухстековый магазинный автомат,
МТ – машина Тьюринга.
Окончание доказательства.
Вывод. Какова – бы ни была сеть Петри машина Тьюринга лучше.
ТЕМА 0.10. МАГАЗИННЫЙ АВТОМАТ
Определени
е.
МАГАЗИННЫМ АВТОМАТОМ называется формальная система
состоящая из 5 (6) объектов
][,,,,, BIPSQAM = , где
{}
m
aaaA ,...,,
21
= - конечный алфавит входных знаков;
{}
110
,...,,
−
=
n
qqqQ - конечное множество состояний магазинного автомата,
где
0
q - заключительное состояние,
1
q - начальное состояние, если не
оговорено особо;
{}
l
sssS ,...,,
21
= - стековый алфавит.
P
- магазинное отображение множества декартового произведения
множеств состояний магазинного автомата, стекового алфавита и входного
алфавита в множество декартового произведения множеств состояний
магазинного автомата, стекового алфавита [и выходного алфавита.]
][:
*
BSQASQP ××→×× .
P
- есть множество команд следующего вида
{
}
][;,,;,|][
*//
BbSAaSsQqqbqasqP
tkjiitikji
∈∈∈∈∈→=
σσ
, где
σ
-
строка в стековом алфавите
*
S .
σ
1
qI = , где
*
1
, SQq ∈∈
σ
- начальная конфигурация магазинного автомата.
{}
r
bbbB ,...,,
21
= - выходной алфавит магазинного автомата.
Не трудно нарисовать внешний вид (структуру) магазинного автомата.
Магазинный автомат состоит из:
1. Устройства управления, реализующего систему команд
P
и имеющего состояние Q .
2. Входной очереди A .
3. Стека
S .
4. Выходной очереди
B
.
Тогда структура магазинного автомата будут выглядеть следующим образом
45
Где из входной очереди
A в устройство управления могут поступать по одному
знаки, то есть обозревается только конец очереди. В выходную очередь
B
может
записываться только один знак. Стек
S обозревается на глубину одного знака, но запись
может производиться на произвольной глубине стека.
Дисциплина доступа к очереди FIFO, к стеку LIFO.
Определение.
КОНФИГУРАЦИЕЙ МАГАЗИННОГО АВТОМАТА
K
называется
выражение
σ
i
qK = , где
i
q - состояние устройства управления,
σ
- состояние стека.
Конфигурация магазинного автомата однозначно определяет его сосстояние.
Отличие магазинного автомата от машины Тьюринга в том, что вместо ленты,
доступной в каждой ячейки, используется стек, доступный только на вершине. Таким
образом изменено устройство чтения и записи знаков.
Процесс занесения на ленту машины Тьюринга исходных данных и чтение
результата моделируется в магазинном автомате
входной и выходной очередью, и в
процессе функционирования, магазинный автомат последовательно извлекает знаки из
входной очереди и записывает знаки в выходную очередь, возможно не вкаждый такт
работы.
e-ПЕРЕМЕЩЕНИЕ МАГАЗИННОГО АВТОМАТА
е-перемещение магазинного автомата существует четырех видов:
1 рода . Осуществляется командами вида ][
/
tiji
bqesq
σ
→ .Не извлекается знак в 1
такт работы магазинного автомата.
2 рода. Осуществляется командами вида
][
/
tiki
bqeaq
σ
→ . Извлекается знак из
входной очереди, но не извлекается знак из стека.
3 рода. Осуществляется командами вида ][
/
tjjkji
bsaasq → . Состояние стека не
изменяется, то есть извлеченный знак
j
s из стека тут же заносится обратно в
стек.
4 рода. Осуществляется командами вида
][
/
tii
bqeeq
σ
→ . В стек заносится строка
σ
Определение.
МНОЖЕСТВО ПРИНИМАЕМЫХ МАГАЗИННЫМ АВТОМАТОМ
СТРОК
()
ML - есть такое множество строк в алфавите A , при подаче
которых на вход магазинного автомата, магазинный автомат перейдет из
начальной конфигурации в заключительную, года состояние устройства
управления
0
q .
/
01
σσ
α
qq ⎯→⎯ , где
*/*
,; SA ∈∈
σσα
.
46
В этом случае строка
α
называется СТРОКОЙ, ПРИНИМАЕМОЙ
(РАСПОЗНАННОЙ) МАГАЗИННЫМ АВТОМАТОМ.
Магазинный автомат распознает (принимает) язык
()
ML если принимает все его строки и
не принимает (не распознает) строки не принадлежащие языку
()
ML .
Пример. Рассмотрим магазинный автомат, распознающий строки, одинаково читаемые
как слева на право, так и справа налево.
IPSQAM ....=
{}
baA ,= - входной алфавит,
{}
210
,, qqqQ = - множество состояний,
{}
BAS ,*,= - алфавит стека, где * - ограничитель стека,
система команд
⎪
⎪
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎧
→
→
→
→
→
→
→
→
→
=
.*
,
,
,|
,|
,|
,|
*,*
*,*
02
22
22
211
211
211
211
11
11
eqeq
eqBbq
eqAaq
eqBBqBbq
eqBAqAbq
eqABqBaq
eqAAqAaq
Bqbq
Aqaq
P
*
1
qI = - начальная конфигурация (* - есть аксиома языка ).
Рассмотрим строку
abba . Подадим ее на вход магазинного автомата
IPSQAM ....= , тогда результат обработки этой строки представим в виде
таблицы.
конфигурация
A
Q S
abba
1
q
*
abb
1
q
*A
ab
1
q
*
B
A
a
2
q
*A
e
2
q
*
e
0
q
Таким образом видно , что данный автомат принял заданную строку.
Очевидно, что рассмотренный автомат принимает все “зеркальные строки”
и является недетерминированным так как
P
не является функцией и переход из
состояния
1
q в состояние
2
q должен произойти на середине строки.
Очевидно, что какой - нибудь из автоматов, полученный в результате
размножения при альтернативном выборе команд остановится, если строка “
зеркальна ” и ни один из автоматов не остановится в противном случае.
ТЕОРЕМА 2.7. О КС грамматике и магазинном автомате.
Для любого языка, порождаемого КС грамматикой существует магазинный автомат,
возможно недетерминированный, распознающий (принимающий) строки этого языка.