Аннотация:
Изучается операция взятия динамической окрестности языка. Доказывается, что эта операция сохраняет регулярность языка. Приводится оценка прироста сложности языка при переходе к его динамической
окрестности.
Ключевые слова:регулярный язык, конечный трансдьюсер, раcстояние Хэмминга, окрестность языка, недетерминированная сложность.
Полный текст:
PDF файл (171 kB)