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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 4. Признаки нераспознаваемости языка конечным автоматом 69
Условия (3) выполняются очевидным образом. ¤
Ввиду предложения 1 доказанную теорему можно сформулиро-
вать так: автомат
e
A(L) — единственный, с точностью до изомор-
физма, минимальный автомат, распознающий язык L.
Из теоремы Майхилла—Нероуда, предложения 1 и теоремы 1 сра-
зу следует, что число состояний любого конечного минимального на-
строенного автомата равно рангу распознаваемого им языка. Но вер-
но и обратное утверждение.
Теорема 2. Если число состояний конечного настроенного ав-
томата (S, δ, s
0
, F ) совпадает с рангом распознаваемого им языка,
то этот автомат — минимальный.
Д о к а з а т е л ь с т в о. Рассмотрим состояния
s
0
δ(p
1
), . . . , s
0
δ(p
n
), (5)
где p
1
, . . . , p
n
— базис отношения ∼ (L). Допустим, что некоторые со-
стояния s
0
δ(p
i
), s
0
δ(p
j
) эквивалентны. Но тогда, как легко проверить,
p
i
∼ p
j
(L), что невозможно для базисных слов. Следовательно, состо-
яния последовательности (5) попарно неэквивалентны и, стало быть,
попарно различны. Поскольку по условию теоремы автомат имеет
n = rk L состояний, то все они присутствуют в (5). Мы доказали оба
условия минимальности. ¤
§ 4. Признаки нераспознаваемости языка
конечным автоматом
Лемма 1. Пусть язык L распознается конечным автоматом.
Тогда существует такое натуральное число n, что любое слово p,
|p| > n, можно представить в виде p = p
1
p
2
p
3
, p
2
6= e, причем для
всех i
p ∈ L ⇒ p
1
p
i
2
p
3
∈ L,
p 6∈ L ⇒ p
1
p
i
2
p
3
6∈ L.
Д о к а з а т е л ь с т в о. Пусть L распознается автоматом
(S, δ, s
0
, F ) с n состояниями, p = x
1
x
2
. . . x
n
— произвольное сло-
во. Среди n + 1 состояний s
0
, s
0
δ(x
1
), s
0
δ(x
1
x
2
), . . . , s
0
δ(x
1
. . . x
n
)
есть два равных. Пусть s
0
δ(x
1
. . . x
m
) = s
0
δ(x
1
. . . x
m
x
m+1
. . . x
m+l
).
Обозначим x
1
. . . x
m
= p
1
, x
m+1
. . . x
m+l
= p
2
, x
m+l+1
. . . x
n
= p
3
.
Не исключено, впрочем, что p
1
или p
3
могут быть пустыми. Ясно,
что s
0
δ(p
1
) = s
0
δ(p
1
p
2
) влечет s
0
δ(p
1
) = s
0
δ(p
1
p
i
2
), а отсюда следу-
ет s
0
δ(p) = s
0
δ(p
1
p
2
p
3
) = s
0
δ(p
1
p
i
2
p
3
) ∀i ∈ N. Таким образом, слова
§ 4. Признаки нераспознаваемости языка                конечным автоматом       69


Условия (3) выполняются очевидным образом. ¤
    Ввиду предложения 1 доказанную теорему можно сформулиро-
                    e
вать так: автомат A(L)    — единственный, с точностью до изомор-
физма, минимальный автомат, распознающий язык L.
    Из теоремы Майхилла—Нероуда, предложения 1 и теоремы 1 сра-
зу следует, что число состояний любого конечного минимального на-
строенного автомата равно рангу распознаваемого им языка. Но вер-
но и обратное утверждение.
   Теорема 2. Если число состояний конечного настроенного ав-
томата (S, δ, s0 , F ) совпадает с рангом распознаваемого им языка,
то этот автомат — минимальный.
    Д о к а з а т е л ь с т в о. Рассмотрим состояния

                             s0 δ(p1 ), . . . , s0 δ(pn ),                    (5)
где p1 , . . . , pn — базис отношения ∼ (L). Допустим, что некоторые со-
стояния s0 δ(pi ), s0 δ(pj ) эквивалентны. Но тогда, как легко проверить,
pi ∼ pj (L), что невозможно для базисных слов. Следовательно, состо-
яния последовательности (5) попарно неэквивалентны и, стало быть,
попарно различны. Поскольку по условию теоремы автомат имеет
n = rk L состояний, то все они присутствуют в (5). Мы доказали оба
условия минимальности. ¤

            § 4. Признаки нераспознаваемости языка
                      конечным автоматом

    Лемма 1. Пусть язык L распознается конечным автоматом.
Тогда существует такое натуральное число n, что любое слово p,
|p| > n, можно представить в виде p = p1 p2 p3 , p2 6= e, причем для
всех i
                     p ∈ L ⇒ p1 pi2 p3 ∈ L,
                           p 6∈ L ⇒ p1 pi2 p3 6∈ L.
    Д о к а з а т е л ь с т в о. Пусть L распознается автоматом
(S, δ, s0 , F ) с n состояниями, p = x1 x2 . . . xn — произвольное сло-
во. Среди n + 1 состояний s0 , s0 δ(x1 ), s0 δ(x1 x2 ), . . . , s0 δ(x1 . . . xn )
есть два равных. Пусть s0 δ(x1 . . . xm ) = s0 δ(x1 . . . xm xm+1 . . . xm+l ).
Обозначим x1 . . . xm = p1 , xm+1 . . . xm+l = p2 , xm+l+1 . . . xn = p3 .
Не исключено, впрочем, что p1 или p3 могут быть пустыми. Ясно,
что s0 δ(p1 ) = s0 δ(p1 p2 ) влечет s0 δ(p1 ) = s0 δ(p1 pi2 ), а отсюда следу-
ет s0 δ(p) = s0 δ(p1 p2 p3 ) = s0 δ(p1 pi2 p3 ) ∀i ∈ N. Таким образом, слова

Страницы