О сравнительной сложности вероятностных и детерминированных автоматов

Поручена оценка сложности вероятностного автомата, представляющего язык с изолированной точкой сечения. Эта оценка зависит от степени изолированности точки сечения и от автоматной структуры языка. Приведены примеры языков, демонстрирующие соотношение между этой оценкой и оценкой, полученной ранее в [1].