Языки и трансляции. Мартыненко Б.К. - 45 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

44
Если бы во множестве T(M) существовали только цепочки длиной l < n, то
по доказанному язык был бы конечен, но это не так. Поэтому существуют и
цепочки длиной l ≥2n. Пусть x — одна из самых коротких цепочек, таких, что
x∈T(M) и | x | ≥ 2n. Очевидно, что существует такое состояние q ∈ Q, что x = x
1
x
2
x
3
,
где 1 ≤ | x
2
| ≤ n, и δ(q
0
, x
1
) = q, δ(q, x
2
) = q, δ(q, x
3
) ∈ F. Но тогда x
1
x
3
∈T(M), поскольку
δ(q
0
, x
1
x
3
) = δ(q
0
, x
1
x
2
x
3
)∈F при том, что | x
1
x
3
| ≥ n (ибо | x | = | x
1
x
2
x
3
| ≥ 2n и 1 ≤ | x
2
| ≤ n).
Поскольку по предположению в T(M) цепочек длины n ≤ l <2n не
существует, то |x
1
x
3
|≥2n. Следовательно, вопреки предположению, что
x = x
1
x
2
x
3
∈T(M) — одна из самых коротких цепочек, длина которой больше
или равна 2n, нашлась более короткая цепочка x
1
x
3
∈T(M) и тоже с длиной,
большей или равной 2n. Это противоречие доказывает необходимость условия 2).
Достаточность условия 2 вытекает из следующих рассуждений. Пусть
существует x∈T(M), причём n ≤|x| <2n. Как и ранее, можем утверждать, что
существует q∈Q, x = x
1
x
2
x
3
, где x
2
≠ε, и δ(q
0
, x
1
) = q, δ(q, x
2
) = q, δ(q, x
3
) ∈F. Но
тогда цепочки вида x
1
x
2
i
x
3
∈T(M) при любом i ≥ 0. Очевидно, что множество
T(M) бесконечно.
Что и требовалось доказать.
Следствие 3.2. Из доказанной теоремы следует существование алгоритмов,
разрешающих вопрос о пустоте, конечности и бесконечности языка, прини-
маемого любым данным конечным автоматом.
Действительно, алгоритм, проверяющий непустоту языка, может система-
тически генерировать все цепочки с постепенно увеличивающейся длиной, но
меньшей n. Каждая из этих цепочек пропускается через автомат. Либо автомат
примет какую-нибудь из этих цепочек, и тогда алгоритм завершится с
положительным ответом, либо ни одна из этих цепочек не будет принята, и
тогда алгоритм завершится с отрицательным результатом. В любом случае
процесс завершается за конечное время.
Алгоритм для проверки бесконечности языка можно построить
аналогичным образом, только он должен генерировать и тестировать цепочки
длиной от n до 2n –1 включительно.
Теорема 3.13. Существует алгоритм для определения, являются ли два
конечных автомата эквивалентными (т.е. принимают ли они один и тот же
язык).
Доказательство. Пусть M
1
и M
2
— конечные автоматы, принимающие
языки L
1
и L
2
соответственно. По теореме 3.7 множество (L
1
∩
2
L
) ∪ (
1
L
∩ L
2
)
принимается некоторым конечным автоматом M
3
.
Легко видеть, что множество T(M
3
)
не пусто тогда и только тогда, когда
L
1
≠ L
2
. Следовательно, согласно теореме 3.12 существует алгоритм для
определения, имеет ли место L
1
= L
2
.
Что и требовалось доказать.

Страницы