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

64                                                  Глава 4. Теория автоматов


   Д о к а з а т е л ь с т в о. Первые два свойства очевидны, пояс-
ним транзитивность. Пусть p ∼ q, q ∼ w и r — произвольное слово.
Транзитивность следует из соотношений:
                    pr ∈ L ⇔ qr ∈ L ⇔ wr ∈ L. ¤
   Лемма 2. Отношение ∼ устойчиво справа относительно кон-
катенации, а именно,
                      p ∼ q ⇒ ∀w ∈ X ∗ pw ∼ qw.

   Д о к а з а т е л ь с т в о. Действительно, для любого слова r
имеем
          (pw)r = p(wr) ∈ L ⇔ (qw)r = q(wr) ∈ L. ¤
    Задача 1. Для любого p ∈ X ∗ определим язык Lp = {q :
pq ∈ L}. Доказать, что p ∼ q(L) ⇔ Lp = Lq .
   Рангом языка L называется число rk L классов эквивалентности
отношения ∼ (L). Другими словами, ранг — это максимальное ко-
личество слов, попарно различимых относительно языка. Если число
классов эквивалентности бесконечно, то полагают rk L = ∞.
   Обозначим через [w] класс неразличимости, содержащий слово
w. Поскольку каждое слово над X лежит точно в одном классе, то
запись [w] однозначно фиксирует класс.
   Лемма 3. Если язык L ⊆ X ∗ распознается конечным настро-
енным автоматом (X, S, δ, s0 , F ) с n состояниями, то rk L 6 n.
     Д о к а з а т е л ь с т в о. Пусть p1 , . . . , pn+1 — произвольно вы-
бранные слова. Среди состояний s0 δ(p1 ), . . . , s0 δ(pn+1 ) есть равные,
пусть s0 δ(pi ) = s0 δ(pj ). Тогда (s0 δ(pi ))δ(r) = (s0 δ(pj ))δ(r), то есть,
s0 δ(pi r) = s0 δ(pj r) для любого слова r. Это значит, что слова pi , pj
неразличимы относительно L. Итак, среди любых n + 1 слов по мень-
шей мере два слова неразличимы. Следовательно, rk L 6 n. ¤
     Критерий распознаваемости языка конечным автоматом был най-
ден Майхиллом и Нероудом в середине прошлого века.
   Теорема 1. Язык L ⊆ X ∗ распознается конечным автоматом
тогда и только тогда, когда он имеет конечный ранг. Если rk L = n,
то существует автомат с n состояниями, распознающий L, при-
чем никакой автомат, распознающий L, не может иметь состоя-
ний меньше, чем n.
                                                 e
   Д о к а з а т е л ь с т в о. Построим автомат A(L), распознающий
язык L. Его состояниями считаем классы неразличимости. Опреде-