Задача разделения строк — задача в теоретической информатике, в которой требуется найти наименьший детерминированный конечный автомат, который ведёт себя по-разному на двух заданных строках, что означает, что автомат принимает одну строку и отвергает другую. Вопрос, насколько большим должен быть такой автомат в худшем случае как функция от длины входных строк, является открытой проблемой.
Пример Две строки, 0010 и 1000, можно различить с помощью автомата, имеющего три состояния, в котором переходы из начального состояния ведут к двум различным состояниям, оба являющихся терминальными. Это означает, что последующие переходы из них всегда возвращаются в то же самое состояние. Состояние автомата фиксирует первый символ входной строки. Если одно из двух терминальных состояний является принимающим, а другое — отклоняющим, то автомат примет только одну из строк 0010 и 1000. Однако эти две строки невозможно различить с помощью любого автомата, имеющего менее трёх состояний.
Упрощение допущений При доказательстве ограничений для данной задачи можно без потери общности считать, что входные данные представлены строками над двухбуквенным алфавитом. Это связано с тем, что если две строки над большим алфавитом различаются, то существует , который отображает их в двоичные строки одинаковой длины, которые также будут различаться. Любой автомат, различающий двоичные строки, может быть преобразован в автомат, различающий исходные строки, без увеличения числа состояний.
Также можно предположить, что две строки имеют одинаковую длину. Для строк разной длины всегда существует простое число простое число , значение которого логарифмически зависит от меньшей из двух входных длин, так что эти длины будут отличаться по модулю . Автомат, подсчитывающий длину входных данных по модулю , может быть использован для различения таких строк. Следовательно, строки разной длины всегда могут быть различены автоматами с небольшим числом состояний.
История и границы Задачу ограничения размера автомата, различающего две заданные строки, впервые сформулировали Горальчик и Кубек, которые показали, что размер автомата всегда сублинеен. Позднее Робсон доказал верхнюю границу для размера автомата, который может потребоваться. Чейз улучшил эту границу до .
Существуют пары входных данных, представляющих собой бинарные строки длины , для которых любой автомат, различающий эти входные данные, должен иметь размер . Сокращение разрыва между этой нижней границей и верхней границей Чейза остается открытой проблемой. предложил приз в 100 фунтов стерлингов за любое улучшение верхней границы Робсона.
Частные случаи Известно, что некоторые частные случаи задачи разделения слов решаются с использованием небольшого числа состояний: Если два двоичных слова имеют разное количество нулей или единиц, их можно различить, подсчитав их веса Хэмминга по модулю простого числа логарифмического размера, используя логарифмическое число состояний. В более общем случае, если некоторая подстрока длиной встречается в двух словах разное число раз, их также можно различить, используя состояний. Если два бинарных слова отличаются друг от друга в первых или последних позициях, их можно различить, используя состояний. Это означает, что почти все пары бинарных слов могут быть различимы с помощью логарифмического числа состояний, поскольку лишь полиномиально малая доля пар не имеет различий в своих начальных позициях. Если два бинарных слова находятся на рассточнии Хэмминга , то существует простое число , такое что , и позиция , в которой две строки отличаются, причём не равно по модулю позиции любого другого отличия. Вычисляя чётность входных символов на позициях, сравнимых с по модулю , можно различить слова с помощью автомата, имеющего состояний.
Примечания
Категория:Конечные автоматы Категория:Нерешённые проблемы информатики