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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

74 Глава 4. Теория автоматов
Рекомендуем читателю проверить, что a
5
b
3
— самое короткое сло-
во, которое один из автоматов переводит в допускающее состояние, а
другой — в недопускающее. Таким образом, языки L
1
и L
2
, распозна-
ваемые автоматами A
1
и A
2
, различны, хотя слова длины не более 7
в них одни и те же.
§ 6. Синтаксический моноид
Пусть дан язык L ⊆ X
∗
. Определим на множестве X
∗
отношение
конгруэнтности ≡ (L) следующим образом. Слова p, q ∈ X
∗
конгру-
энтны относительно L, если
∀r
1
, r
2
∈ X
∗
(r
1
pr
2
∈ L ⇔ r
1
qr
2
∈ L).
Прямо из определений отношений ≡ (L) и ∼ (L) видно, что
конгруэнтность — более сильное свойство, чем неразличимость:
p ≡ q(L) ⇒ p ∼ q(L).
Лемма 1. Отношение конгруэнтности относительно языка
является эквивалентностью.
Доказательство сходно с доказательством леммы 1 §2.
Для конгруэнтности справедливо более сильное утверждение, чем
лемма 2 §2.
Лемма 2. Если p
1
≡ q
1
(L), p
2
≡ q
2
(L), то p
1
p
2
≡ q
1
q
2
(L).
Д о к а з а т е л ь с т в о. Согласно определению конгруэнтности
p
1
p
2
≡ q
1
p
2
(L), q
1
p
2
≡ q
1
q
2
(L). Используя транзитивность отношения
≡ (L), получаем p
1
p
2
≡ q
1
q
2
(L). ¤
Определим синтаксический моноид языка L ⊆ X
∗
. Элементы
синтаксического моноида — это классы конгруэнтности ≡ (L). Опре-
делим умножение классов: если hpi и hqi — классы, содержащие сло-
ва p и q, то hpihqi = hpqi. В силу леммы 2 произведение классов не
зависит от выбора их представителей и потому определено коррект-
но. Легко проверяется ассоциативноcть умножения классов и то, что
класс hei — единица относительно умножения. Итак, классы конгру-
энтности образуют моноид, который и называется синтаксическим
моноидом языка L.
Лемма 3. Пусть (S, δ, s
0
, F ) — минимальный автомат, рас-
познающий язык L. Преобразования δ(p) и δ(q) совпадают тогда и
только тогда, когда слова p и q конгруэнтны относительно L, то
есть,
δ(p) = δ(q) ⇔ p ≡ q(L).
74                                               Глава 4. Теория автоматов


Рекомендуем читателю проверить, что a5 b3 — самое короткое сло-
во, которое один из автоматов переводит в допускающее состояние, а
другой — в недопускающее. Таким образом, языки L1 и L2 , распозна-
ваемые автоматами A1 и A2 , различны, хотя слова длины не более 7
в них одни и те же.

                  § 6. Синтаксический моноид

   Пусть дан язык L ⊆ X ∗ . Определим на множестве X ∗ отношение
конгруэнтности ≡ (L) следующим образом. Слова p, q ∈ X ∗ конгру-
энтны относительно L, если
                ∀r1 , r2 ∈ X ∗ (r1 pr2 ∈ L ⇔ r1 qr2 ∈ L).
   Прямо из определений отношений ≡ (L) и ∼ (L) видно, что
конгруэнтность — более сильное свойство, чем неразличимость:
                        p ≡ q(L) ⇒ p ∼ q(L).
     Лемма 1. Отношение конгруэнтности относительно языка
является эквивалентностью.
     Доказательство сходно с доказательством леммы 1 §2.
     Для конгруэнтности справедливо более сильное утверждение, чем
лемма 2 §2.
     Лемма 2. Если p1 ≡ q1 (L), p2 ≡ q2 (L), то p1 p2 ≡ q1 q2 (L).
     Д о к а з а т е л ь с т в о. Согласно определению конгруэнтности
p1 p2 ≡ q1 p2 (L), q1 p2 ≡ q1 q2 (L). Используя транзитивность отношения
≡ (L), получаем p1 p2 ≡ q1 q2 (L). ¤
     Определим синтаксический моноид языка L ⊆ X ∗ . Элементы
синтаксического моноида — это классы конгруэнтности ≡ (L). Опре-
делим умножение классов: если hpi и hqi — классы, содержащие сло-
ва p и q, то hpihqi = hpqi. В силу леммы 2 произведение классов не
зависит от выбора их представителей и потому определено коррект-
но. Легко проверяется ассоциативноcть умножения классов и то, что
класс hei — единица относительно умножения. Итак, классы конгру-
энтности образуют моноид, который и называется синтаксическим
моноидом языка L.
     Лемма 3. Пусть (S, δ, s0 , F ) — минимальный автомат, рас-
познающий язык L. Преобразования δ(p) и δ(q) совпадают тогда и
только тогда, когда слова p и q конгруэнтны относительно L, то
есть,
                           δ(p) = δ(q) ⇔ p ≡ q(L).

Страницы