Дискретная математика: графы и автоматы. Альпин Ю.А - 62 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

62 Глава 4. Теория автоматов
a b
1
2
3
4
2 4
2 3
4 3
4 4
Рис. 2
Перейдем к более удобной форме записи: вместо δ(s, x) = s
0
бу-
дем писать sδ(x) = s
0
. Тем самым каждой букве x сопоставляется
преобразование δ(x) : S → S. Слову p = x
1
x
2
. . . x
k
сопоставим про-
изведение преобразований
δ(p) = δ(x
1
)δ(x
2
) . . . δ(x
k
).
Положим, что δ(e) — тождественное преобразование. Таким образом,
конкатенации pq слов p и q отвечает произведение соответствующих
преобразований, то есть, δ(pq) = δ(p)δ(q). Тем самым, множество
{δ(p), p ∈ X
∗
} преобразований множества S образует мультиплика-
тивный моноид. Назовём его моноидом автомата (X, S, δ).
Фактически выше мы определили гомоморфизм δ моноида слов
X
∗
в моноид преобразований, совершаемых этими словами в про-
странстве состояний автомата.
Если автомат находится в состоянии s и получает на входе
слово p = x
1
x
2
. . . x
k
, то он переходит в состояние sδ(x
1
), за-
тем в sδ(x
1
)δ(x
2
) = sδ(x
1
x
2
) и так далее, наконец, в состояние
sδ(x
1
)δ(x
2
) . . . δ(x
k
) = sδ(p). На графе автомата состоянию s и слову
p отвечает единственный путь
s, sδ(x
1
), . . . , sδ(p). (1)
Назовем автомат (X, S, δ) настроенным, если в нем выделено
некоторое начальное состояние s
0
и некоторое подмножество F ⊆ S
допускающих состояний. Мы будем рассматривать и “полунастроен-
ные” автоматы вида (X, S, δ, F ) с фиксированным множеством F
допускающих состояний, но без выделенного начального состояния.
Говорят, что настроенный автомат (X, S, δ, s
0
, F ) распознаёт язык
L ⊆ X
∗
, если
s
0
δ(p) ∈ F ⇔ p ∈ L.
Таким образом, распознаваемый язык состоит из тех и только тех
слов, которые переводят автомат из начального в какое-либо допус-
кающее состояние.
62                                                         Глава 4. Теория автоматов




                                                       a   b
                                              1        2   4
                                              2        2   3
                                              3        4   3
                                              4        4   4

                                   Рис. 2

   Перейдем к более удобной форме записи: вместо δ(s, x) = s0 бу-
дем писать sδ(x) = s0 . Тем самым каждой букве x сопоставляется
преобразование δ(x) : S → S. Слову p = x1 x2 . . . xk сопоставим про-
изведение преобразований
                      δ(p) = δ(x1 )δ(x2 ) . . . δ(xk ).
Положим, что δ(e) — тождественное преобразование. Таким образом,
конкатенации pq слов p и q отвечает произведение соответствующих
преобразований, то есть, δ(pq) = δ(p)δ(q). Тем самым, множество
{δ(p), p ∈ X ∗ } преобразований множества S образует мультиплика-
тивный моноид. Назовём его моноидом автомата (X, S, δ).
    Фактически выше мы определили гомоморфизм δ моноида слов
  ∗
X в моноид преобразований, совершаемых этими словами в про-
странстве состояний автомата.
    Если автомат находится в состоянии s и получает на входе
слово p = x1 x2 . . . xk , то он переходит в состояние sδ(x1 ), за-
тем в sδ(x1 )δ(x2 ) = sδ(x1 x2 ) и так далее, наконец, в состояние
sδ(x1 )δ(x2 ) . . . δ(xk ) = sδ(p). На графе автомата состоянию s и слову
p отвечает единственный путь
                          s, sδ(x1 ), . . . , sδ(p).                            (1)
   Назовем автомат (X, S, δ) настроенным, если в нем выделено
некоторое начальное состояние s0 и некоторое подмножество F ⊆ S
допускающих состояний. Мы будем рассматривать и “полунастроен-
ные” автоматы вида (X, S, δ, F ) с фиксированным множеством F
допускающих состояний, но без выделенного начального состояния.
Говорят, что настроенный автомат (X, S, δ, s0 , F ) распознаёт язык
L ⊆ X ∗ , если
                      s0 δ(p) ∈ F ⇔ p ∈ L.
Таким образом, распознаваемый язык состоит из тех и только тех
слов, которые переводят автомат из начального в какое-либо допус-
кающее состояние.

Страницы