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

§ 2. Критерий распознаваемости языка конечным автоматом             65


лим функцию перехода. Для любого класса [w] и любой буквы x поло-
       e = [wx]. Корректность этого определения обеспечивается
жим [w]δ(x)
леммой 2. Для слова p = x1 x2 . . . xk имеем:
                     e = [w]δ(x
                  [w]δ(p)   e 1 )δ(x
                                 e 2 ) . . . δ(x
                                             e k) =

                   e 2 ) . . . δ(x
             [wx1 ]δ(x         e k ) = [wx1 x2 . . . xk ] = [wp].
В качестве начального состояния возьмем класс [e]. Класс [w] считаем
допускающим состоянием, если w ∈ L, то есть, [w] ∈ Fe ⇔ w ∈ L.
Это определение корректно, так как слова из класса неразличимости
либо все принадлежат L, либо все не принадлежат. Из предыдущей
цепочки равенств при w = e для произвольного слова p получаем
   e
[e]δ(p)                            e
        = [p] и, следовательно, [e]δ(p) ∈ Fe ⇔ p ∈ L. Итак, автомат
 e
A(L)  распознает язык L. Если число rk L его состояний конечно, то
любой автомат, распознающий L, не может иметь меньше состояний
по лемме 3. Если же rk L = ∞, то в силу той же леммы язык L не
распознается никаким конечным автоматом. ¤
   Задача 2. Докажите, что любой конечный язык распознаётся
некоторым конечным автоматом.
    Пример 1. Пусть язык L состоит из слов, начинающихся с буквы
a и заканчивающихся буквой b, то есть
                          L = {apb : p ∈ X ∗ }.
Рассмотрим слова e, a, b, ab. Легко заметить, что слово e отличимо от
слов a и ab словом b, поскольку eb = b 6∈ L, ab ∈ L, abb = ab2 ∈ L.
Слова e и b различимы словом ab, так как eab = ab ∈ L, bab 6∈ L.
Рассуждая аналогично, можно установить, что любые два слова из
указанной четверки различимы. Теперь заметим, что любое слово,
длина которого больше единицы, имеет один из трех типов: apa, apb,
bp. Слова первого типа эквивалентны a, второго — ab, третьего —
b. Следовательно, классов отношения ∼ (L) всего четыре: [e], [a],
[b], [ab]. Соответствующий автомат изображён на рис. 3. Начальное
состояние — [e], допускающее состояние одно — [ab].
     Опишем некоторый систематический способ построения автомата
 e
A(L). Пусть дан язык L ⊆ X ∗ . Множество слов W ⊆ X ∗ называется
базисом отношения ∼ (L), если
     а) любые два слова из W различимы относительно L,
     б) любое слово из X ∗ эквивалентно некоторому слову из W .