Теория алгоритмов и формальных языков. Мелихов А.Н - 67 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Граф автомата A показан на рис.3.11:
рис.3.11
Пусть на вход автомата, установленного в начальное состояние Qq
∈
0
подается входное
слово d=
2
x
1
x
2
x
1
x
1
x
1
x
3
x. Автомат переработает d в выходное слово
β
=
1
y
2
y
2
y
1
y
2
y
1
y
1
y и окажется снова в состоянии
0
q . Поэтому можно записать
)(df=
β
. Если на вход автомата подать входные слова
1
d =
1
x
2
x
3
x или
2
d =
3
x
1
x
2
x
1
x
2
x ,
то на выходе не образуется выходных слов, так как переходы по букве
3
x в слове
1
d и по
последней букве в
2
x в слове
2
d не определены в таблице 3.10 (а). Поэтому слова
1
d и
2
d
являются недопустимыми и относятся к области запрета. В качестве заключительного
состояния автомата A выбрано состояние
0
q . Отметим еще раз, что в качестве
заключительных состояний может быть выбрано любое подмножество Q’
Q≡ .
Говорят, что конечный автомат с выходами индуцирует (или реализует) частичное
отображение f множества
*
x
V и
*
y
V
, которое удовлетворяет следующим условиям:
1)
любому допустимому входному слову
*
x
V∈
α
отображение f сопоставляет
выходное слово
*
)(
y
Vf ∈
α
, имеющее одинаковую длину с
α
;
2)
если
α
- допустимое входное слово, а
1
α
- начальный отрезок (вхождение) слова
α
, то )(
1
α
f существует и совпадает с некоторым начальным отрезком слова
)(
α
f .
Эти условия называются условиями автоматности отображения.
3.6 Алгебра событий. Представление событий в автоматах.
Пусть
A
- конечный автомат с входным алфавитом
{
}
mx
xxxV ,,,
21
K
=
и выходным
алфавитом
{}
ny
yyyV ,,,
21
K=
, который индуцирует частичное автоматное отображение
f
множества
*
x
V в
*
y
V
.
Событием
i
P , представленным (допустимым) в автомате
A
выходнам сигналом
{}
),,2,1( nIiy
i
K=∈ , называется множество всех входных слов
*
x
V∈
α
этого автомата, для
которых слово )(
α
f определено и оканчивается
i
y . Если
y
VY
≡
'- некоторое
подмножество выходных сигналов, то событием, представленным в автомате A
множества '
Y
, называется объединение событий, представляемых всеми элементами этого
множества. В том случае, когда '
Y
совпадает с
y
V , соответствующие ему событие
называется каноническим множеством событий
n
PPP ,,,
21
K автомата
A
. Например
{
}
313121231213121233321
,,,;, xxxxxxxxxxxxxxxxxxxxP = и
{
}
213131121211212
,,,; xxxxxxxxxxxxxxP
=
-
события, представление выходными буквами и в автомате
A
из примера 3.10.
Сформулируйте предложение, которое подведет базу под изучение автоматных
отображений.
22
/ yx
22
/ yx
11
/ yx
21
/ yx
13
/ yx
0
q
1
q
13
/ yx
2
q
12
/ yx

Страницы