Стохастичность языков, распознаваемых двусторонними конечными вероятностными автоматами

Доказывается, что двусторонними конечными вероятностными автоматами можно распознавать только стохастические языки, т.е. возможности односторонних и двусторонних конечных вероятностных автоматов с неизолированной точкой сечения по распознаванию языков совпадают. Даются оценки увеличения числа состояний при переходе от двустороннего автомата к одностороннему, распознающему тот же язык.