close

Вход

Забыли?

вход по аккаунту

?

Конечно-нестационарные недетерминированные автоматы со случайным входом.

код для вставкиСкачать
УДК 519.71
Вестник СПбГУ. Сер. 1. 2011. Вып. 2
КОНЕЧНО-НЕСТАЦИОНАРНЫЕ
НЕДЕТЕРМИНИРОВАННЫЕ АВТОМАТЫ
СО СЛУЧАЙНЫМ ВХОДОМ∗
М. К. Чирков1 , А. С. Шевченко2
1. С.-Петербургский государственный университет,
д-р физ.-мат. наук, профессор, mkchirk@mail.ru
2. С.-Петербургский государственный университет,
аспирант, annion@yandex.ru
1. Введение. В общей теории автоматных моделей подробно исследован детерминированный автомат с дополнительным «случайным» входом, который является одним
из удобных способов моделирования вероятностных автоматов и представляемых ими
вероятностных языков. Методы моделирования вероятностного автомата с помощью
детерминированного автомата со случайным входом подробно описаны, например, в работах [1–4]. Возможность моделирования вероятностных языков стационарными недетерминированными автоматами со случайным входом проанализирована в работах [5,
6]; показано,что такие автоматы также представляют вероятностные языки.
Для автоматного моделирования совокупностей нестационарных, одновременно
действующих, взаимосвязанных дискретных систем и протекающих в них процессов была введена и исследована более сложная нестационарная автоматная модель —
обобщенный конечно-нестационарный недетерминированный автомат [7]. В данной работе исследована новая нестационарная автоматная модель — обобщенный конечнонестационарный недетерминированный автомат со случайным входом. При этом установлена и доказана эквивалентность по представляемому языку таких автоматов известным типам стационарных вероятностных автоматных моделей.
2. Основные понятия. Детерминированный конечный автомат задается как
совокупность Adet = X, A, Y, a0 , f, ϕ алфавитов входных символов X, состояний A и
выходных символов Y, начального состояния a0 ∈ A, однозначной функции переходов
f : A × X → A и однозначной функции выходов, которая в случае автоматов Мили
задается как функция ϕ : A × X → Y.
Детерминированный автомат со случайным входом Ainp представляет собой детерминированный конечный автомат, имеющий два входных канала, причем входные
символы на один из каналов подаются с заданными вероятностями от источника случайных символов, и задается как система
Ainp = Z × X, A, Y, a0 , Ψ, μ,
где Z = {z0 , z1 , . . . , zq−1 }, Ψ : A × Z × X → A × Y, а μ = (μ0 , μ1 , . . . , μq−1 ) есть распределение вероятностей воздействия на автомат символов из Z, не зависящее от номера
такта, состояния автомата, входных символов из X и выходных из Y.
Если алфавит Y исключить из определения автомата, то получим абстрактный
детерминированный автомат со случайным входом Ainp = Z × X, A, a0 , Ψ, μ.
Вероятностный (стохастический) конечный автомат Apr определяется как совокупность Apr = X, A, Y, p, {P(xs , yl )} входного алфавита X, |X| = n, алфавита
∗ Работа
c
104
выполнена при финансовой поддержке РФФИ (грант № 10-01-00310).
М. К. Чирков, А. С. Шевченко, 2011
состояний A, |A| = m, и выходного алфавита Y, |Y | = h, начального распределения
вероятностей состояний p = (p0 , p1 , . . . , pm−1 ) и системы (m × m)-матриц вероятностей
переходов
Pij (xs , yl ) = P (aj yl |ai xs ),
P(xs , yl ) = (Pij (xs , yl ))m,m ,
где ai , aj ∈ A, xs ∈ X, yl ∈ Y. Соответственно, если исключить из определения выходной алфавит Y, получим абстрактный вероятностный конечный автомат
Apr = X, A, p, {P(xs )}.
Будем рассматривать алгебраическую систему (булеву решетку) D = ({0, 1}, ∨, &, ≤),
т. е. множество {0, 1} с логическими операциями дизъюнкции ∨ (в дальнейшем условно
«сложение»), конъюнкции & (в дальнейшем условно «умножение») и обычным упорядочением. Условимся соответственно применять обозначения D1,m , Dm,1 и Dm,n для
множеств всех m-мерных векторов-строк, векторов-столбцов и всех (m × n)-матриц с
элементами из {0, 1}.
Обобщенным стационарным недетерминированным автоматом, заданным над D,
называют систему
And = X, A, Y, r, {D(xs , yl )}, q,
1,m
(1)
где r ∈ D
— вектор-строка начальных состояний (начальный вектор), q ∈ D
—
вектор-столбец конечных состояний (финальный вектор) и {D(xs , yl )} ∈ Dm,m — совокупность матриц переходов, xs ∈ X, yl ∈ Y .
Обобщенным недетерминированным конечным автоматом со случайным входом
будем называть систему
m,1
Asnd = Z × X, A, Y, r, {D(zg , xs , yl )}, q, μ,
(2)
представляющую собой недетерминированный автомат, на который одновременно воздействуют пары входных символов из конечного множества Z × X, где {D(zg , xs , yl )},
D(zg , xs , yl ) ∈ Dm,m , есть совокупность qnh матриц переходов, zg ∈ Z, xs ∈ X, yl ∈ Y, и
μ = (μ0 , μ1 , . . . , μq−1 ) есть распределение вероятностей воздействия на автомат различных символов из множества Z в одном такте, не зависящее от номера такта, состояния
автомата, входных символов из X и от выходных из Y. Таким образом, автомат Asnd
представляет собой недетерминированный конечный автомат, имеющий два входных канала,
причем входные символы на один из них подаются с заданными вероятностями μ.
Если алфавит Y исключить из определения автомата, то полученный автомат назовем абстрактным недетерминированным автоматом со случайным входом
Asnd = Z × X, A, r, {D(zg , xs )}, q, μ,
(3)
где {D(zg , xs )} ∈ Dm,m — совокупность qn матриц переходов, zg ∈ Z, xs ∈ X.
Элементарной недетерминированной автоматной структурой, заданной над D,
условимся называть систему
A(i,j) = X (i,j) , Ai , Aj , Y (i,j) , {D(i,j) (xs , yl )},
(4)
где X (i,j) ⊆ X; Ai , Aj , A — алфавиты состояний, Ai , Aj ⊆ A; |Ai | = mi , |Aj | = mj ;
Y (i,j) ⊆ Y, и {D(i,j) (xs , yl )} — совокупность матриц переходов D(i,j) (xs , yl ) ∈ Dmi ,mj
из состояний алфавита Ai в состояния алфавита Aj , соответствующих парам (xs , yl ),
xs ∈ X (i,j) , yl ∈ Y (i,j) .
105
Элементарной недетерминированной автоматной структурой со случайным входом, заданной над D, условимся называть систему
(i,j)
Ainp = Z × X (i,j) , Ai , Aj , Y (i,j) , {D(i,j) (zg , xs , yl )}, μ,
(5)
где Z = {z0 , z1 , . . . , zq−1 }, μ = (μ0 , μ1 , . . . , μq−1 ) есть распределение вероятностей воздействия на автоматную структуру различных символов из Z, а {D(i,j) (zg , xs , yl )} —
совокупность матриц переходов D(i,j) (zg , xs , yl ) ∈ Dmi ,mj из состояний алфавита Ai
в состояния алфавита Aj , соответствующих тройкам (zg , xs , yl ), zg ∈ Z, xs ∈ X (i,j) ,
yl ∈ Y (i,j) .
Пусть задано конечное множество элементарных недетерминированных автоматных структур A = {A(i,j) } вида (4), входной алфавит X = ∪(i,j) X (i,j) , выходной алфавит Y = ∪(i,j) Y (i,j) и конечное упорядоченное множество финальных векторов-столбцов Q = {q(0) , q(1) , . . . , q(k) }, q(i) ∈ Dmi ,1 , i = 0, k, некоторые из которых могут быть
«нулевыми», т. е. могут не содержать элементов, равных 1.
Обобщенным конечно-нестационарным недетерминированным автоматом, заданным над D, назовем систему
And = X, A, Y, r, G(G, C, c0 , f ), Q,
(6)
где G есть структурный граф автомата (конечный, ориентированный, нагруженный
граф), имеющий:
— конечное множество вершин C = {c0 , c1 , . . . , ck }, каждой из которых ci ∈ C приписан соответствующий алфавит состояний Ai и финальный вектор-столбец (иначе,
вектор-столбец конечных состояний) q(i) ∈ Q, i = 0, k, а также для выделенной начальной вершины c0 с алфавитом состояний A0 задан вектор-строка начальных состояний
r ∈ D1,m0 ;
— конечное множество G направленных ребер gij , соединяющих некоторые вершины
графа ci , cj ∈ C;
— однозначную функцию f : G → A, приписывающую каждому ребру gij ∈ G заданную
элементарную автоматную структуру A(i,j) ∈ A.
Обобщенным конечно-нестационарным недетерминированным автоматом со случайным входом (рис. 1) назовем, соответственно, систему
Asnd = Z × X, A , Y, r, G(G, C, c0 , f ), Q, μ,
(7)
где однозначная функция f : G → A каждому ребру gij ∈ G графа G приписывает
(i,j)
заданную элементарную автоматную структуру со случайным входом Ainp вида (5) из
(i,j)
заданного множества A = {Ainp } таких структур.
Если же алфавит Y исключить из определения автомата, то полученный автомат
назовем абстрактным конечно-нестационарным недетерминированным автоматом
со случайным входом
Asnd = Z × X, A, r, G(G, C, c0 , f ), Q, μ.
μ
X
Z
-
nd
A
Рис. 1.
106
-Y
(8)
3. Представление языков автоматами. В теории обобщенных автоматов [8],
задаваемых над каким-либо частично упорядоченным полукольцом R = (R, +, ·, ≤),
обобщенным языком в алфавите X называют однозначное отображение Z : X ∗ → R,
задаваемое значениями характеристической функции ΦZ (w) ∈ R, w ∈ X ∗ . В частном
случае полукольца — булевой решетки D = ({0, 1}, ∨, &, ≤), характеристическая функция принимает значения ΦZ (w) ∈ {0, 1}, w ∈ X ∗ , и задает подмножество слов Z ⊆ X ∗ ,
т. е. обычно определяемый в теории автоматов «четкий» язык Z в алфавите X.
Пусть задан обобщенный стационарный недетерминированный автомат And (1).
Обозначим через (w, v) пару слов длины t в алфавитах X, Y , w = xs1 xs2 . . . xst , v =
yl1 yl2 . . . ylt , а множества всех слов в алфавитах X, Y — соответственно X ∗ , Y ∗ . Обобщенным недетерминированным отображением, индуцируемым автоматом And , называют отображение Φnd : X ∗ × Y ∗ → {0, 1}, определяемое выражением
⎧
t
⎪
⎨ r D(xs , yl )q при w = v = t,
τ
τ
τ =1
Φnd (w, v) =
(9)
⎪
⎩
0
при w = v,
где t = 0, 1, 2, . . . , а под сложением и умножением элементов матриц и векторов понимаются операции ∨ и &.
Пусть для автомата And выделено подмножество Y (к) ⊆ Y его выходных символов.
Говорят, что автомат And представляет подмножеством конечных выходных символов Y (к) язык Z, если для характеристической функции подмножества Z выполняется
<
<
⎧
Φnd (w, v yl ) при |w| = |v yl | = t,
⎨
t−1
(к)
v ∈Y
y
∈Y
l
ΦZ (w) =
(10)
⎩
0
при |w| = |v yl |
при всех w ∈ X ∗ , |w| = t = 0, 1, . . .
Пусть задан обобщенный недетерминированный автомат со случайным входом Asnd
(2) и выделено подмножество Y (к) его выходных символов. Условимся, что обобщенный
язык Z, определяемый характеристической функцией ΦZ : X ∗ → [0, 1], представлен
в Asnd подмножеством Y (к) (иначе, представлен недетерминированным автоматом
со случайным входом Asnd ), если выполняется
ΦZ (w) =
P (yl |w)
(11)
(
к
)
yl ∈Y
для всех w ∈ X ∗ , |w| = t, t = 0, 1, . . . , где P (yl |w) есть вероятность выдачи автоматом Asnd в последнем такте t символа yl с учетом распределения вероятностей μ при
входном слове w длины t. В случае абстрактного недетерминированного автомата со
случайным входом Asnd (3) обобщенный язык Z представлен в Asnd подмножеством
конечных состояний A(к) ⊆ A и определяется значениями характеристической функции
ΦZ (w) =
P (ai |w)qi , qi = 1 ⇔ ai ∈ A(к) ,
i
для всех w ∈ X ∗ , |w| = y, t = 0, 1, . . . , где P (ai |w) есть вероятность перехода автомата
Asnd в последнем такте t в состояние ai с учетом распределения вероятностей μ, а qi —
i-й элемент финального вектора q.
Заметим, что обобщенные вероятностные языки, представляемые вероятностными
автоматами, определяются таким же образом [4].
107
Пусть задан обобщенный конечно-нестационарный недетерминированный автомат
And (6). Выделим в его структурном графе G какую-либо вершину ci и пусть этой вершине приписан финальный вектор q(i) ∈ Q. Рассмотрим один из путей Ω0i , ведущий из
начальной вершины c0 в вершину ci ∈ C графа и проходящий через вершины c0 =
= ci0 , . . . , cit = ci . Выпишем последовательность элементарных автоматных структур, отмечающих ребра, образующие этот путь. Пусть это будут A(i0 ,i1 ) , A(i1 ,i2 ) , . . . ,
A(it−1 ,it ) , то есть путь проходит через t отмеченных ребер графа. Рассмотрим любую
пару слов (w, v), w = xs1 xs2 . . . xst , xsτ ∈ X (iτ −1 ,iτ ) , v = yl1 yl2 . . . ylt , ylτ ∈ Y (iτ −1 ,iτ ) , одной длины t в алфавитах X (iτ −1 ,iτ ) и Y (iτ −1 ,iτ ) , τ = 1, t. Множество всех пар таких слов
назовем множеством допустимых пар слов для пути Ω0i и обозначим Zдоп (i) (при
этом считается, что «пустые» слова e, не содержащие ни одной буквы, всегда допустимы, то есть (e, e) ∈ Zдоп (0) ). Весом отображения слова w в слово v, порождаемого путем
Ω0i структурного графа G автомата And при заданном r ∈ D1,m0 , назовем величину
⎧
t
⎪
⎨ r
D(iτ −1 ,iτ ) (xsτ , ylτ )q(it ) при (w, v) ∈ Zдоп (i) ,
(i)
τ =1
Φnd (w, v) =
⎪
⎩
0
при (w, v) ∈ Zдоп (i) .
Рассмотрим теперь всевозможные вершины структурного графа. Пусть Ω(w,
v) есть
множество всех путей Ω0i в структурном графе из начальной вершины c0 в какие-либо
вершины ci ∈ C, для которых пара слов (w, v) является допустимой. Множество всех
v) не пусто, условимся называть
таких пар слов (w, v) ∈ X ∗ × Y ∗ , для которых Ω(w,
множеством допустимых для автомата And пар слов и обозначать его Zдоп .
Обобщенным отображением, индуцируемым автоматом And при заданном r, назовем отображение Φnd : X ∗ × Y ∗ → {0, 1}, определяемое выражением
=
(i)
Φnd (w, v),
(12)
Φnd (w, v) =
Ω(w,v)
где логическое суммирование берется по всем путям (последовательностям вершин
v). Учитывая выражение (12), если для автомата And выдеci0 , ci1 , . . . , cit ) Ω0it ∈ Ω(w,
(к)
лено подмножество Y
⊆ Y, то характеристическая функция языка Z, представленного автоматом And , определяется формулой (10).
4. Постановка задачи. Задан обобщенный конечно-нестационарный недетерминированный автомат со случайным входом; требуется выяснить, какие языки представимы таким типом автоматной модели, доказать эквивалентность этого автомата по
представляемому языку обобщенному стационарному недетерминированному автомату
со случайным входом и абстрактному вероятностному автомату, получив оценки требуемого числа состояний, и предложить алгоритм преобразования обобщенного конечнонестационарного недетерминированного автомата со случайным входом в абстрактный
вероятностный автомат.
5. Эквивалентные преобразования автоматов. Условимся в дальнейшем под
эквивалентностью автоматов подразумевать их эквивалентность по представляемому
языку, т. е. в общем случае будем говорить, что автоматы A и B представляющие,
соответственно, языки ZA и ZB , эквивалентны, если ZA = ZB . При этом заметим,
что требование эквивалентности автоматов по индуцируемому отображению является
более жестким.
108
Теорема 1. Для каждого обобщенного конечно-нестационарного недетерминированного автомата со случайным входом Asnd вида (7) может быть построен эквивалентный ему обобщенный стационарный #
недетерминированный автомат со случайk
ным входом Bsnd вида (2), имеющий m = i=0 |Ai | состояний.
Доказательство. Исходя из теоремы, изложенной в работе [7], для каждого обобщенного конечно-нестационарного недетерминированного автомата And может быть
построен эквивалентный#
ему обобщенный стационарный недетерминированный автоk
мат And , имеющий m = i=0 |Ai | состояний. В случае автомата со случайным входом
доказательство в основном содержит те же шаги, что и доказательство вышеуказанной
теоремы, и сводится к следующему. Пусть задан автомат Asnd (7), некоторые элементы
которого условимся для уточнения снабдить нижними индексами A. Определим новый
алфавит состояний B = {b0 , b1 , . . . , bm } = {B0 , B1 , . . . , Bk }, где |Bi | = |Ai | = mi , i = 0, k,
и построим автомат вида (2)
Bsnd = Z × X, B, Y, rB , {DB (zg , xs , yl )}, qB , μ,
m−m0
> ?@ A
(0)
(1)
(k)
где rB = (rA , 0, . . . , 0), qB = ((qA )T , (qA )T , . . . , (qA )T )T .
Определим пустой элемент ε и функцию f˜A такую, что
f˜A : C × C → A ∪ {ε}.
(13)
При этом f˜A (ci , cj ) = A1(i,j) = ε, если в структурном графе G отсутствует ребро
gij , и f˜A (ci , cj ) = A1(i,j) = fA (ci , cj ) = A(i,j) , если ребро gij присутствует, т. е. gij ∈ G.
Структурному графу автомата Asnd с учетом (13) соответствует матрица графа (см.
табл. 1), где все A1(i,j) ∈ A ∪ {ε}.
Таблица 1. Матрица графа GA
f˜A
c0
c1
...
ck
c0
(0,0)
1
A
1(1,0)
A
c1
(0,1)
1
A
1(1,1)
A
...
...
1(k,0)
A
...
1(k,1)
A
...
...
...
...
ck
(0,k)
1
A
1(1,k)
A
...
1(k,k)
A
Теперь, если заменить в табл. 1 все ci на Bi , |Bi | = |Ai | и, соответственно, каждое
(i,j)
1
1 (i,j) (zg , xs , yl ), где
A
на матрицу переходов D
A
1 (i,j)
D
A (zg , xs , yl ) =
⎧ (i,j)
⎪
D
(zg , xs , yl ), если f˜A (ci , cj ) = A(i,j) , zg ∈ Z, xs ∈ X (i,j) , yl ∈ Y (i,j) ,
⎪
⎪ A
⎨
=
O,
если f˜A (cj , cj ) = A(i,j) , но xs ∈ X (i,j) или yl ∈ Y (i,j) ,
⎪
⎪
⎪
⎩
O,
если f˜A (ci , cj ) = ε,
(14)
то в результате получим следующее представление матриц DB (zg , xs , yl ) (см. табл. 2).
Докажем эквивалентность автоматов Asnd и Bsnd . При t = 0 из (9) и (12) следу(0)
ет, что Φsnd (e, e) = rB qB = rA qA = Φ̃snd (e, e). Условимся в дальнейшем для удобgs (в матрицах
ства обозначать пары входных символов (zg , xs ) одним символом x
109
Таблица 2. Клеточное представление матриц DB (zg , xs , yl )
DB (zg , xs , yl )
B1
(0,1)
1
DA (zg , xs , yl )
1 (1,1) (zg , xs , yl )
D
...
B1
B0
(0,0)
1
DA (zg , xs , yl )
1 (1,0) (zg , xs , yl )
D
...
...
...
...
Bk
1 (k,0) (zg , xs , yl )
D
A
1 (k,1) (zg , xs , yl )
D
A
...
B0
A
A
Bk
(0,k)
1
DA (zg , xs , yl )
1 (1,k) (zg , xs , yl )
D
...
...
A
...
(k,k)
1
DA (zg , xs , yl )
DB возможно обозначение (g, s, l) вместо, соответственно, (zg , xs , yl )). В этом случае
входное слово w выглядит следующим образом: w = x
g1 s1 x
g2 s2 . . . x
gt st . Если t > 0 и
w=x
g1 s1 x
g2 s2 . . . x
gt st , v = yl1 yl−2 . . . ylt , то из (9), (12), (14) и табл. 2 следует, что
Φsnd (w, v) = rB
t
DB (zgτ , xsτ , ylτ )qB = (rA , 0, . . . , 0)
τ =1
(0)
DB (zgτ , xsτ , ylτ )×
τ =1
(1)
(k)
× ((qA )T , (qA )T , . . . , (qA )T )T =
⎧
⎪
⎨
=
t
⎪
⎩
=
...
i1
<
Ω(w,v)
rA
t
τ =1
(i
DAτ −1
=
it
,iτ )
0
rA
t
1 (iτ −1 ,iτ ) (zgτ , xsτ , ylτ )q(it ) =
D
A
A
τ =1
(i )
(zgτ , xsτ , ylτ )qAt
при (w, v) ∈ Zдоп ,
при (w, v) ∈ Zдоп ,
т. е. получили, что Φsnd = Φ̃snd , а это значит, что автоматы Asnd и Bsnd , имеющие
одни и те же Z и μ, при любом выборе Y (к) в соответствии с (10), (11) представляют
одинаковые языки, т. е. они эквивалентны. Теорема доказана.
Следствие. Для каждого абстрактного обобщенного конечно-нестационарного
недетерминированного автомата со случайным входом Asnd вида (8) может быть
построен эквивалентный ему обобщенный стационарный абстрактный недетерми#k
нированный автомат со случайным входом Bsnd вида (3), имеющий m =
i=0 |Ai |
состояний.
Данное утверждение непосредственно следует из теоремы 1, поскольку при ее доказательстве из автомата Asnd вида (8) получается автомат Bsnd вида (3). Воспользуемся
теперь одним из результатов работы [5].
Теорема 2. Для любого обобщенного недетерминированного конечного автомата
со случайным входом Asnd (2), имеющего m = |A| состояний и h = |Y | выходных
символов и представляющего подмножеством Y (к) обобщенный язык Z, может быть
построен эквивалентный ему абстрактный конечный вероятностный автомат Apr ,
который имеет m̃ ≤ 2mh состояний.
Таким образом, на основе теорем 1, 2 может быть сформулирован один из основных
результатов данной работы.
Теорема 3. Для любого обобщенного конечно-нестационарного недетерминированного автомата со случайным входом Asnd вида (7), имеющего h = |Y | выходных символов и представляющего подмножеством Y (к) обобщенный язык Z, может быть
построен эквивалентный ему абстрактный конечный вероятностный автомат Apr ,
#k
который имеет m
≤ 2hm состояний, где m = i=0 |Ai |.
Доказательство. Из доказательств теорем 1, 2 следует возможность последовательного построения
Asnd →1) Bsnd →2) Apr :
110
#k
1) по теореме 1 с увеличением количества состояний до i=0 |Ai |;
2) по теореме 2 с увеличением количества состояний максимально до 2hm , где m =
#k
= i=0 |Ai |;
что определяет процесс синтеза эквивалентного абстрактного вероятностного автомата
Apr для любого заданного обобщенного конечно-нестационарного недетерминированного автомата со случайным
входом Asnd с увеличением количества состояний максимум
#k
до 2hm , где m = i=0 |Ai |. Теорема доказана.
6. Алгоритм. Из полученных результатов следует, что для синтеза абстрактного
вероятностного автомата по заданному обобщенному конечно-нестационарному недетерминированному автомату со случайным входом необходимо выполнить следующее:
1) исходный обобщенный конечно-нестационарный недетерминированный автомат
со случайным входом Asnd преобразовать в обобщенный стационарный недетерминированный автомат со случайным входом Bsnd (согласно методу, предложенному в теореме 1);
2) удалить недостижимые состояния полученного автомата и произвести его минимизацию [9];
3) полученный обобщенный недетерминированный автомат со случайным входом
преобразовать в абстрактный стационарный недетеминированный автомат со случайным входом (см. работу [5]);
4) полученный абстрактный недетерминированный автомат со случайным входом
преобразовать в абстрактный стационарный детерминированный автомат со случайным входом [5];
5) для полученного абстрактного детерминированного автомата со случайным входом построить абстрактный стационарный вероятностный автомат [1–5];
6) произвести минимизацию полученного абстрактого вероятностного автомата известными способами (например, см. [4]).
7. Пример. Пусть задан абстрактный конечно-нестационарный недетерминированный автомат со случайным входом Asnd (8), у которого X (i,j) = X = {x0 , x1 }, i, j ∈
∈ {0, 1, 2}, Z = {z0 , z1 }, |A0 | = 3, |A1 | = |A2 | = 2, μ = (0, 3; 0, 7),
rA = (1 0
0) ,
(0)
qA =
0
1
0
,
(1)
qA =
0
1
,
(2)
qA =
1
,
0
структурный граф GA которого имеет вид
A(1,2)
........................................................................ A
.............. 2
..................
.
.
.
A
A(2,2)
.
.
.
.
.
.
.
1
.
..........
..
-.r.........................
jr
.................
.
.
.
(2,1)
.
.
.
.
.
.
.
.
.. .
.............. ......3
c1 Y.........................................A
............................................................ c2
.
.............
...........
..............
............
................
.
(0,2)
.
.
.
.
.
.
.
.
.
.
.
.
.....................
...............
..................................A
.................................................
A0
A(0,1)
..r
........
........
c0 ............................
(i,j)
а матрицы DA (g, s)
следующие:
⎛
1
(0,1)
DA (0, 0) = ⎝1
0
элементарных автоматных структур, отмечающих ребра графа,
⎞
0
0⎠ ,
0
⎛
0
(0,1)
DA (0, 1) = ⎝1
1
⎞
1
0⎠ ,
0
⎛
⎞
1 0
(0,1)
DA (1, 0) = ⎝0 0⎠ ,
0 1
111
⎛
(0,1)
DA (1, 1)
⎞
0 0
= ⎝0 1 ⎠ ,
0 1
⎛
0
(0,2)
DA (1, 0) = ⎝0
1
(1,2)
DA
(0, 1) =
1 0
,
1 0
1
0
0
(2,1)
DA (1, 1) =
0
(2,1)
DA
(0, 0) =
⎞
1
0⎠ ,
0
0
,
1
1
,
0
(0,2)
DA (0, 0)
⎛
0
= ⎝1
0
⎞
0
0⎠ ,
1
⎛
(0,2)
DA (0, 1)
⎞
0 1
(0,2)
DA (1, 1) = ⎝0 1⎠ ,
0 0
⎞
0 0
= ⎝0 1 ⎠ ,
1 0
⎛
(1,2)
DA
(1, 0) =
(1,2)
DA
1
,
0
0
0
(1,2)
DA
(0, 0) =
0 0
,
1 0
(1, 1) =
0 1
,
1 0
0 1
0
(2,1)
,
DA (1, 0) =
1 0
1
0 1
0
(2,2)
(2,2)
DA (0, 0) =
,
DA (0, 1) =
1 0
0
1 0
1 0
(2,2)
(2,2)
DA (1, 0) =
,
DA (1, 1) =
.
0 0
1 0
(2,1)
DA
(0, 1) =
0
,
0
1
,
1
В соответствии с п. 1 алгоритма построим автомат Bsnd . Для начального и финального векторов получаем
qB = (0, 1, 0, 0, 1, 1, 0)T .
rB = (1, 0, 0, 0, 0, 0, 0),
По структурному графу строим соответствующую ему матрицу:
f˜A
c0
c1
c2
(0,1)
(0,2)
A
A
c0
ε
c1
ε
ε
A(1,2)
c2
ε
A(2,1)
A(2,2)
Далее, помощью табл. 2 строим клеточное представление матриц DB (g, s):
DB (g, s)
B0
B0
O
B1
O
B2
O
B1
(0,1)
DA
(g, s)
O
(2,1)
DA
(g, s)
B2
(0,2)
(g, s)
(1,2)
(g, s)
(2,2)
(g, s)
DA
DA
DA
В соответствии с пп. 2 и 3 алгоритма после удаления недостижимых состояний и
проведения минимизации данного автомата (см. [9]) окончательно получаем автомат
Csnd = Z × X, C, rC , {DC (g, s)}, qC , μ,
112
где C = {c0 , c1 , c2 , c3 , c4 }, rC = (1, 0, 0, 0, 0), qC = (0, 0, 1, 1, 0)T , μ = (0, 3; 0, 7),
⎛
0
⎜0
⎜
DC (0, 0) = ⎜0
⎝0
0
⎛
0
⎜0
⎜
DC (1, 0) = ⎜0
⎝0
0
⎞
1
0
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0⎟
⎟
0⎟ ,
1⎠
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
1⎟
⎟
0⎟ ,
0⎠
0
⎞
⎛
0
⎜0
⎜
DC (0, 1) = ⎜0
⎝0
0
⎛
0
⎜0
⎜
DC (1, 1) = ⎜0
⎝0
0
⎞
0
0
0
0
1
1
0
0
1
0
0
1
1
0
0
0
0⎟
⎟
0⎟ ,
1⎠
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
1
1
1⎟
⎟
0⎟ ,
0⎠
0
⎞
находящийся в минимальной форме стационарным абстрактным недетерминированным автоматом со случайным входом, эквивалентным исходному автомату Asnd .
Далее согласно п. 4 преобразуем полученный автомат в абстрактный детерминированный автомат со случайным входом Ainp = Z × X, C, c0 , Ψ, μ, где Ψ :
Ψ
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
x
00
c1
c7
c2
c5
c6
c6
c9
c7
c6
c12
c12
c12
c12
c6
c5
x
01
c2
c3
c3
c8
c5
c9
c11
c7
c9
c12
c13
c12
c12
c9
c11
x
10
c5
c4
c7
c3
c1
c5
c3
c7
c1
c9
c14
c14
c9
c5
c10
x
11
c4
c4
c3
c6
c3
c10
c6
c7
c3
c11
c6
c6
c11
c10
c11
Затем полученный автомат согласно п. 5 преобразуем в стационарный вероятностный абстрактный автомат Apr = X, A, p, {P(xs )}, e(к) , где
p = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), e(к) = q = (0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1)T и,
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
P(x0 ) = ⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0, 3
0
0
0
0, 7
0
0
0
0, 7
0
0
0
0
0
0
0 0
0
0 0 0, 7
0 0, 3 0
0 0, 7 0
0 0
0
0 0
0
0 0, 7 0
0 0
0
0 0
0
0 0
0
0 0
0
0 0
0
0 0
0
0 0
0
0 0
0
0, 7
0
0
0, 3
0
0, 7
0
0
0
0
0
0
0
0, 7
0, 3
0
0 0 0
0
0 0, 3 0 0
0
0 0, 7 0 0
0
0
0 0 0
0
0, 3 0 0 0
0
0, 3 0 0 0
0
0
0 0 0, 3 0
0
1 0 0
0
0, 3 0 0 0
0
0
0 0 0, 7 0
0
0 0 0
0
0
0 0 0
0
0
0 0 0, 7 0
0, 3 0 0 0
0
0
0 0 0 0, 7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0, 3
0, 3
0, 3
0, 3
0
0
⎞
0 0
0 0 ⎟
⎟
0 0 ⎟
⎟
0 0 ⎟
⎟
0 0 ⎟
⎟
0 0 ⎟
⎟
0 0 ⎟
⎟
0 0 ⎟
⎟,
0 0 ⎟
⎟
0 0 ⎟
⎟
0 0, 7 ⎟
⎟
0 0, 7 ⎟
⎟
0 0 ⎟
⎟
0 0 ⎠
0 0
113
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
P(x1 ) = ⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 0, 3 0 0, 7 0
0 0 0, 3 0, 7 0
0 0
1
0
0
0 0
0
0
0
0 0 0, 7 0 0, 3
0 0
0
0
0
0 0
0
0
0
0 0
0
0
0
0 0 0, 7 0
0
0 0
0
0
0
0 0
0
0
0
0 0
0
0
0
0 0
0
0
0
0 0
0
0
0
0 0
0
0
0
0
0
0
0, 7
0
0
0, 7
0
0
0
0, 7
0, 7
0
0
0
0 0
0
0
0
0
0
0 0
0
0
0
0
0
0 0
0
0
0
0
0
0 0, 3 0
0
0
0
0
0 0
0
0
0
0
0
0 0 0, 3 0, 7 0
0
0
0 0
0
0 0, 3 0
0
1 0
0
0
0
0
0
0 0 0, 3 0
0
0
0
0 0
0
0 0, 7 0, 3 0
0 0
0
0
0
0 0, 3
0 0
0
0
0 0, 3 0
0 0
0
0 0, 7 0, 3 0
0 0 0, 3 0, 7 0
0
0
0 0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟.
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
Полученный автомат Apr эквивалентен по представляемому обобщенному вероятностному языку исходному конечно-нестационарному абстрактному недетерминированному автомату со случайным входом.
9. Заключение. В работе доказано, что для любого обобщенного конечно-нестационарного недетерминированного автомата со случайным входом Asnd может быть
построен эквивалентный ему по представляемому обобщенному вероятностному языку
стационарный абстрактный вероятностный автомат Apr . Предложен подробный алгоритм такого преобразования, проиллюстрированный на примере.
Результат имеет важное значение для разработки в дальнейшем специальных методов решения обратной задачи синтеза обобщенных конечно-нестационарных недетерминированных автоматных моделей со случайным входом по заданным обобщенным
вероятностным языкам и позволяет по-новому подойти к проблеме прикладного математического моделирования таких языков.
Литература
1. Ченцов В. М. Синтез стохастического автомата // Проблемы синтеза цифровых автоматов. М.: Наука, 1967. С. 135–144.
2. Чирков М. К. Основы общей теории конечных автоматов. Л.: Изд-во Ленингр. ун-та.
1975. 280 с.
3. Бухараев Р. Г. Основы теории вероятностных автоматов. М., 1985. 288 с.
4. Пономарева А. Ю., Чирков М. К. Стационарные детерминированные и вероятностные
автоматы (Теория автоматных моделей). СПб.: Изд-во С.-Петерб. ун-та, 2008. 248 с.
5. Чирков М. К., Шевченко А. С. О языках, представимых обобщенными недетерминированными автоматами со случайным входом // Математические модели. Теория и приложения.
Вып. 8. СПб.: Изд-во «Золотое сечение», 2007. С. 110–124.
6. Shevchenko A. S., Tchirkov M. K. On simulation of stochatic languages by nondeterministic
automata // Procceding of the 6th St.Petesburg Workshop on Simulation. St.Petersburg, June 28 —
Jule 4, 2009. Vol. 2. St.Petersburg. VVM com. Ltd., 2009. P. 869–874.
7. Мбайтар Ж.-Б., Чирков М. К. Абстрактный анализ конечно-нестационарных недетерминированных автоматов // Математические модели. Теория и приложения. Вып. 8. СПб.:
Изд-во «Золотое сечение», 2007. С. 34–46.
114
8. Чирков М. К., Кабаве М. Абстрактный анализ обобщенных конечных автоматов // Теория и приложения дискретных систем. СПб.: Изд-во С.-Петерб. ун-та, 1995. С. 3–36.
9. Пономарева А. Ю., Сандрыкина Н. В., Чирков М. К. Оптимизация абстрактной структуры недетерминированных автоматов // Математические модели. Теория и приложения.
Вып. 3. СПб.: НИИХ СПбГУ, 2003. С. 94–102.
Статья поступила в редакцию 2 ноября 2010 г.
115
Документ
Категория
Без категории
Просмотров
4
Размер файла
356 Кб
Теги
случайных, недетерминированных, входом, автомати, конечно, нестационарные
1/--страниц
Пожаловаться на содержимое документа