ВУЗ:
Составители:
Рубрика:
§ 6. Синтаксический моноид 75
Д о к а з а т е л ь с т в о. Если δ(p) = δ(q), то при любых r
1
, r
2
∈ X
∗
имеем:
δ(r
1
pr
2
) = δ(r
1
)δ(p)δ(r
2
) = δ(r
1
)δ(q)δ(r
2
) = δ(r
1
qr
2
).
Отсюда следует цепочка импликаций
s
0
δ(r
1
pr
2
) = s
0
δ(r
1
qr
2
) ⇒ (r
1
pr
2
∈ L ⇔ r
1
qr
2
∈ L) ⇒ p ≡ q(L).
Теперь пусть δ(p) 6= δ(q), то есть, sδ(p) 6= sδ(q) для некоторого
состояния s ∈ S. Ввиду связности автомата найдётся такое слово r
1
,
что s
0
δ(r
1
) = s. Следовательно, имеем
s
0
δ(r
1
)δ(p) = s
0
δ(r
1
p) 6= s
0
δ(r
1
q) = s
0
δ(r
1
)δ(q).
В силу приведённости автомата неравные состояния неэквива-
лентны. Поэтому существует такое слово r
2
, что лишь одно из со-
стояний
s
0
δ(r
1
p)δ(r
2
), s
0
δ(r
1
q)δ(r
2
)
принадлежит F . А это значит, что слова p и q не конгруэнтны отно-
сительно языка L. ¤
Теорема 1. Моноид минимального автомата (S, δ, s
0
, F ), рас-
познающего язык L, изоморфен синтаксическому моноиду языка L.
Д о к а з а т е л ь с т в о. Определим отображение моноида ав-
томата в синтаксический моноид, положив δ(p) 7→ hpi. Корректность
определения этого отображения и то, что оно инъективно, следует
из леммы 3, а сюръективность очевидна. Осталась лёгкая проверка
условия гомоморфизма:
δ(p)δ(q) = δ(pq) 7→ hpqi = hpihqi.
Итак, отображение, сопоставляющее преобразованию δ(p) класс
конгруэнтности hpi, в случае минимального автомата является изо-
морфизмом моноидов. ¤
Следствие 1. Синтаксический моноид языка L содержит ко-
нечное число элементов тогда и только тогда, когда язык L распо-
знаётся конечным автоматом. При этом, если ранг языка равен n,
то число элементов синтаксического моноида не больше n
n
.
Д о к а з а т е л ь с т в о. Предположим, что синтаксический
моноид языка L содержит m элементов, то есть, имеется m классов
конгруэнтности ≡ (L). Тогда среди любых m+1 слов из X
∗
есть хотя
§ 6. Синтаксический моноид 75
Д о к а з а т е л ь с т в о. Если δ(p) = δ(q), то при любых r1 , r2 ∈ X ∗
имеем:
δ(r1 pr2 ) = δ(r1 )δ(p)δ(r2 ) = δ(r1 )δ(q)δ(r2 ) = δ(r1 qr2 ).
Отсюда следует цепочка импликаций
s0 δ(r1 pr2 ) = s0 δ(r1 qr2 ) ⇒ (r1 pr2 ∈ L ⇔ r1 qr2 ∈ L) ⇒ p ≡ q(L).
Теперь пусть δ(p) 6= δ(q), то есть, sδ(p) 6= sδ(q) для некоторого
состояния s ∈ S. Ввиду связности автомата найдётся такое слово r1 ,
что s0 δ(r1 ) = s. Следовательно, имеем
s0 δ(r1 )δ(p) = s0 δ(r1 p) 6= s0 δ(r1 q) = s0 δ(r1 )δ(q).
В силу приведённости автомата неравные состояния неэквива-
лентны. Поэтому существует такое слово r2 , что лишь одно из со-
стояний
s0 δ(r1 p)δ(r2 ), s0 δ(r1 q)δ(r2 )
принадлежит F . А это значит, что слова p и q не конгруэнтны отно-
сительно языка L. ¤
Теорема 1. Моноид минимального автомата (S, δ, s0 , F ), рас-
познающего язык L, изоморфен синтаксическому моноиду языка L.
Д о к а з а т е л ь с т в о. Определим отображение моноида ав-
томата в синтаксический моноид, положив δ(p) 7→ hpi. Корректность
определения этого отображения и то, что оно инъективно, следует
из леммы 3, а сюръективность очевидна. Осталась лёгкая проверка
условия гомоморфизма:
δ(p)δ(q) = δ(pq) 7→ hpqi = hpihqi.
Итак, отображение, сопоставляющее преобразованию δ(p) класс
конгруэнтности hpi, в случае минимального автомата является изо-
морфизмом моноидов. ¤
Следствие 1. Синтаксический моноид языка L содержит ко-
нечное число элементов тогда и только тогда, когда язык L распо-
знаётся конечным автоматом. При этом, если ранг языка равен n,
то число элементов синтаксического моноида не больше nn .
Д о к а з а т е л ь с т в о. Предположим, что синтаксический
моноид языка L содержит m элементов, то есть, имеется m классов
конгруэнтности ≡ (L). Тогда среди любых m + 1 слов из X ∗ есть хотя
