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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

70 Глава 4. Теория автоматов
p
1
p
i
2
p
3
переводят автомат из начального в одно и то же состояние. Ес-
ли оно допускающее, то все эти слова лежат в L, в противном случае
все они не лежат в L. ¤
Из леммы 1 немедленно следует признак нераспознаваемости:
Следствие 1. Если для сколь угодно большого числа n найдется
слово p ∈ L, |p| > n, такое, что при любом представлении p =
p
1
p
2
p
3
найдется показатель i, при котором p
1
p
i
2
p
3
6∈ L, то язык L
не распознается никаким конечным автоматом.
Очевидный пример — язык L
3
. При любом представлении слова
p = a
k
b
k
∈ L в виде p = p
1
p
2
p
3
(p
2
6= e) имеем p
1
p
2
2
p
3
6∈ L. Следова-
тельно, L
3
— нераспознаваемый язык.
Докажем нераспознаваемость языка L
4
. Предположим противное.
Тогда для достаточно большого k существует такое представление
a
k
2
= a
k
1
a
k
2
a
k
3
(k
2
> 1), что слова a
k
1
a
ik
2
a
k
3
, a
k
1
a
(i+1)k
2
a
k
3
принад-
лежат L
4
при i = 1, 2, . . . . Разность длин этих слов равна k
2
для
любого i. Однако разность между длинами соседних слов из L
4
рав-
на (k +1)
2
−k
2
= 2k + 1 и она стремится к бесконечности при k → ∞.
Пришли к противоречию.
Теперь рассмотрим язык L
5
, состоящий из слов вида a
k
, где
k — простое число. Он не распознается конечным автоматом, по-
скольку при сколь угодно большом простом k и любом разложе-
нии a
k
= a
k
1
a
k
2
a
k
3
(k
2
> 1) слово a
k
1
a
ik
2
a
k
3
не принадлежит L
5
при
i = k
1
+ k
3
> 0 (число k
1
+ (k
1
+ k
3
)k
2
+ k
3
— не простое). Если же
k
1
+ k
3
= 0, то число ik
2
— не простое при любом i > 2.
Еще одно сильное средство установления нераспознаваемости
языков конечными автоматами состоит в следующем. Пусть L и M
— непересекающиеся языки. Скажем, что слова p, q различимы от-
носительно языков L и M, если для некоторого r
pr ∈ L, qr ∈ M, или qr ∈ L, pr ∈ M. (1)
Лемма 2. Если существует бесконечное множество слов, по-
парно различимых относительно языков L и M, то любой язык P ,
такой, что
L ⊆ P, M ∩ P = ∅, (2)
не распознается конечным автоматом.
Д о к а з а т е л ь с т в о почти очевидно, поскольку если для
слов p, q выполняется (1), то pr ∈ P , q r 6∈ P или pr 6∈ P , qr ∈
P . То есть, слова, различимые относительно пары L, M, различимы
относительно любого языка P , удовлетворяющего условию (2). ¤
70                                                Глава 4. Теория автоматов


p1 pi2 p3 переводят автомат из начального в одно и то же состояние. Ес-
ли оно допускающее, то все эти слова лежат в L, в противном случае
все они не лежат в L. ¤
      Из леммы 1 немедленно следует признак нераспознаваемости:
      Следствие 1. Если для сколь угодно большого числа n найдется
слово p ∈ L, |p| > n, такое, что при любом представлении p =
p1 p2 p3 найдется показатель i, при котором p1 p2i p3 6∈ L, то язык L
не распознается никаким конечным автоматом.
      Очевидный пример — язык L3 . При любом представлении слова
p = ak bk ∈ L в виде p = p1 p2 p3 (p2 6= e) имеем p1 p22 p3 6∈ L. Следова-
тельно, L3 — нераспознаваемый язык.
      Докажем нераспознаваемость языка L4 . Предположим противное.
Тогда для достаточно большого k существует такое представление
   2
ak = ak1 ak2 ak3 (k2 > 1), что слова ak1 aik2 ak3 , ak1 a(i+1)k2 ak3 принад-
лежат L4 при i = 1, 2, . . . . Разность длин этих слов равна k2 для
любого i. Однако разность между длинами соседних слов из L4 рав-
на (k + 1)2 − k 2 = 2k + 1 и она стремится к бесконечности при k → ∞.
Пришли к противоречию.
      Теперь рассмотрим язык L5 , состоящий из слов вида ak , где
k — простое число. Он не распознается конечным автоматом, по-
скольку при сколь угодно большом простом k и любом разложе-
нии ak = ak1 ak2 ak3 (k2 > 1) слово ak1 aik2 ak3 не принадлежит L5 при
i = k1 + k3 > 0 (число k1 + (k1 + k3 )k2 + k3 — не простое). Если же
k1 + k3 = 0, то число ik2 — не простое при любом i > 2.
      Еще одно сильное средство установления нераспознаваемости
языков конечными автоматами состоит в следующем. Пусть L и M
— непересекающиеся языки. Скажем, что слова p, q различимы от-
носительно языков L и M , если для некоторого r
                  pr ∈ L, qr ∈ M, или qr ∈ L, pr ∈ M.                   (1)


    Лемма 2. Если существует бесконечное множество слов, по-
парно различимых относительно языков L и M , то любой язык P ,
такой, что
                         L ⊆ P, M ∩ P = ∅,                      (2)
не распознается конечным автоматом.
    Д о к а з а т е л ь с т в о почти очевидно, поскольку если для
слов p, q выполняется (1), то pr ∈ P , qr 6∈ P или pr 6∈ P , qr ∈
P . То есть, слова, различимые относительно пары L, M , различимы
относительно любого языка P , удовлетворяющего условию (2). ¤

Страницы