Доказательство. Если qi rk+1 qj, то qi и qj неотличимы на входных словах, длина которых не превосходит k+1
Если qi rk+1 qj, то qi и qj неотличимы на входных словах, длина которых не превосходит k+1. Поэтому qi и qj неотличимы и на dc[ словах длины k. Следовательно, rk 
rk+1.
Если qi e qj, то состояния qi и qj - неотличимые на всех словах, в том числе на словах, длина которых не превосходит k. Поэтому rk e.
Лемма доказана.
Лемма 2
Если для некоторого числа k справедливо равенство rk = rk+1, то rk = e.
Дата добавления: 2015-09-18; просмотров: 494;