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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 5. Свойства операций над языками 73
Теорема 3. Пусть автоматы (4) с числом состояний n
1
и n
2
распознают языки L
1
и L
2
. Если слова длины 6 n
1
n
2
− 1 в L
1
и L
2
одни и те же, то L
1
= L
2
.
Д о к а з а т е л ь с т в о. Условие теоремы означает, что не
существует слова длины 6 n
1
n
2
− 1, которое переводит настроенный
автомат (6) в допускающее состояние. Поскольку этот автомат имеет
n
1
n
2
состояний, то в силу леммы 1 таких слов нет вообще, то есть,
язык, распознаваемый автоматом (6), пустой. Стало быть, L
1
= L
2
. ¤
Поскольку множество слов длины не более 6 n
1
n
2
− 1 конечно,
то теорема 3 обеспечивает возможность проверить эквивалентность
автоматов за конечное число действий.
Пример 1. Рассмотрим автоматы на рис. 5. Положим, что у
Рис. 5
обоих автоматов начальное состояние 1 является единственным до-
пускающим состоянием. На рис. 6 изображён граф настроенного ав-
томата (6) (проведены лишь дуги, ведущие из состояний, достижи-
мых из начального состояния (1,1), допускающие состояния обведены
кружк´ами).
Рис. 6
§ 5. Свойства операций над языками                               73


    Теорема 3. Пусть автоматы (4) с числом состояний n1 и n2
распознают языки L1 и L2 . Если слова длины 6 n1 n2 − 1 в L1 и L2
одни и те же, то L1 = L2 .
    Д о к а з а т е л ь с т в о. Условие теоремы означает, что не
существует слова длины 6 n1 n2 − 1, которое переводит настроенный
автомат (6) в допускающее состояние. Поскольку этот автомат имеет
n1 n2 состояний, то в силу леммы 1 таких слов нет вообще, то есть,
язык, распознаваемый автоматом (6), пустой. Стало быть, L1 = L2 . ¤
    Поскольку множество слов длины не более 6 n1 n2 − 1 конечно,
то теорема 3 обеспечивает возможность проверить эквивалентность
автоматов за конечное число действий.
    Пример 1. Рассмотрим автоматы на рис. 5. Положим, что у




                                     Рис. 5


обоих автоматов начальное состояние 1 является единственным до-
пускающим состоянием. На рис. 6 изображён граф настроенного ав-
томата (6) (проведены лишь дуги, ведущие из состояний, достижи-
мых из начального состояния (1,1), допускающие состояния обведены
кружка́ми).




                                     Рис. 6

Страницы