![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Доказательство. Пусть rk = rk+1. Покажем, что rk+1 = rk+2
Пусть rk = rk+ 1 . Покажем, что rk+1 = rk+ 2 . То есть если состояния q i и q j являются (k + 1) -неотличимыми, то они являются и (k + 2) -неотличимыми. Пусть a Так как rk = rk+1и q i 1 rk q j 1, то по условию леммы q i 1 rk+1 q j 1. Поэтому слово Следовательно, q i и q j являются k + 2 -неотличимыми. Поэтому rk+1= rk+2. Повторяя проведенные рассуждения, можно показать, что rk+1 = rk+2 = rk+3 = rk+4...
Следовательно, для любого входного слова Поэтому, если состояния q i и q j неотличимы на словах длины k, то они неотличимы на словах любой конечной длины, т.е. q i и q j являются неотличимыми. Следовательно, rk = e.
|