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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 2. Критерий распознаваемости языка конечным автоматом 63
На графе автомата словам распознаваемого языка отвечают в
точности те пути (1), которые начинаются в вершине s
0
, а закан-
чиваются в одной из вершин множества F .
Вернувшись к примерам автоматов, приведенным выше, нетруд-
но увидеть, что первый из них с настройкой s
0
= 1, F = {1, 5, 7}
распознаёт язык L
1
, а второй автомат с настройкой s
0
= 1, F = {3}
распознаёт язык L
2
. Однако существуют языки, нераспознаваемые
никакими конечными автоматами.
Предложение 2. Язык L
3
= {a
k
b
k
: k = 1, 2, . . . } не распозна-
ётся никаким конечным автоматом.
Д о к а з а т е л ь с т в о. Предположим противное: язык L
3
распознаётся некоторым автоматом (X, S , δ, s
0
, F ) с n состояниями.
Рассмотрим состояния
s
0
δ(a), s
0
δ(a
2
), . . . , s
0
δ(a
n+1
).
В этой последовательности n + 1 элементов, значит, для некоторых
неравных k, l имеем s
0
δ(a
k
) = s
0
δ(a
l
). Но тогда, с одной стороны,
(s
0
δ(a
k
))δ(b
k
) = s
0
δ(a
k
b
k
) ∈ F, (2)
а с другой,
(s
0
δ(a
l
))δ(b
k
) = s
0
δ(a
l
b
k
) 6∈ F. (3)
Но состояния в (2) и (3) равны. Полученное противоречие завершает
доказательство. ¤
Возникает естественный вопрос: как устроены языки, распозна-
ваемые конечными автоматами?
§ 2. Критерий распознаваемости языка конечным
автоматом
Будем говорить, что слова p, q ∈ X
∗
различимы словом r ∈ X
∗
относительно языка L ⊆ X
∗
, если pr ∈ L, qr 6∈ L или pr 6∈ L,
qr ∈ L. Если для p и q различающих слов не существует, то будем го-
ворить, что слова p и q неразличимы относительно языка L и писать
p ∼ q(L) или p ∼ q, когда язык L фиксирован. Таким образом,
p ∼ q(L) ⇔ ∀r ∈ X
∗
(pr ∈ L ⇔ qr ∈ L).
Лемма 1. Отношение неразличимости слов относительно
языка рефлексивно, симметрично и транзитивно, то есть явля-
ется отношением эквивалентности.
§ 2. Критерий распознаваемости языка конечным автоматом            63


   На графе автомата словам распознаваемого языка отвечают в
точности те пути (1), которые начинаются в вершине s0 , а закан-
чиваются в одной из вершин множества F .
   Вернувшись к примерам автоматов, приведенным выше, нетруд-
но увидеть, что первый из них с настройкой s0 = 1, F = {1, 5, 7}
распознаёт язык L1 , а второй автомат с настройкой s0 = 1, F = {3}
распознаёт язык L2 . Однако существуют языки, нераспознаваемые
никакими конечными автоматами.
   Предложение 2. Язык L3 = {ak bk : k = 1, 2, . . . } не распозна-
ётся никаким конечным автоматом.
   Д о к а з а т е л ь с т в о. Предположим противное: язык L3
распознаётся некоторым автоматом (X, S, δ, s0 , F ) с n состояниями.
Рассмотрим состояния
                    s0 δ(a), s0 δ(a2 ), . . . , s0 δ(an+1 ).
В этой последовательности n + 1 элементов, значит, для некоторых
неравных k, l имеем s0 δ(ak ) = s0 δ(al ). Но тогда, с одной стороны,
                    (s0 δ(ak ))δ(bk ) = s0 δ(ak bk ) ∈ F,         (2)
а с другой,
                    (s0 δ(al ))δ(bk ) = s0 δ(al bk ) 6∈ F.        (3)
Но состояния в (2) и (3) равны. Полученное противоречие завершает
доказательство. ¤
   Возникает естественный вопрос: как устроены языки, распозна-
ваемые конечными автоматами?

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

    Будем говорить, что слова p, q ∈ X ∗ различимы словом r ∈ X ∗
относительно языка L ⊆ X ∗ , если pr ∈ L, qr 6∈ L или pr 6∈ L,
qr ∈ L. Если для p и q различающих слов не существует, то будем го-
ворить, что слова p и q неразличимы относительно языка L и писать
p ∼ q(L) или p ∼ q, когда язык L фиксирован. Таким образом,
              p ∼ q(L)    ⇔     ∀r ∈ X ∗ (pr ∈ L ⇔ qr ∈ L).
   Лемма 1. Отношение неразличимости слов относительно
языка рефлексивно, симметрично и транзитивно, то есть явля-
ется отношением эквивалентности.

Страницы