Доброго времени суток!
Есть обширная теория по распознанию цепочки на основе заданной грамматики, методы анализа также отвечают на вопрос выводима ли цепочка в данной граматике. А есть ли какие-нибудь методы, позволяющие решить такой вопрос: есть цепочка, определить может ли она является подцепочкой корректной цепочки.

Например, есть язык a^n, b^n (n > 0) - цепочки вида ab, aabb, aaabbb, ...
На входе есть цепочка aab - она не принадлежит этому языку, но может быть подцепочкой корректной цепочки, например, aabb (добавили букву b справа).
Или, например, есть цепочка aba, очевидно, что она сама не принадлежит языку и никакая цепочка ее содержащая тоже языку не принадлежит.

Единственное, что приходит на ум - это модификация анализатора снизу вверх.

Буду рад ссылкам и просто идеям. Спасибо!

Странный вопрос. Вообще-то, такой анализ является неотъемлемой частью разбора строки.
Нужно просто следить за состоянием автомата, анализирующего строку (для грамматики (a*n)(b*n) подойдет автомат с магазинной памятью). Если строка переводит автомат в недопускающее состояние (либо для очередного символа отсутствует правило перехода), то она не принадлежит языку и не является префиксом корректной строки. Если строка переводит автомат в допускающее состояние и стек пуст, то строка принадлежит языку. В остальных случаях строка не принадлежит языку, но является корректным префиксом.

Спасибо, за ответ, для определения корректных префиксов такой способ действительно подходит.

Но я, наверно, не очень хорошо задал вопрос, вообще говоря, интересует проверка любой подстроки, находящейся не обязательно в начале или в конце цепочки.

Для наглядности переделаю пример: язык a^n b^n c^n
цепочка bbbc - она может содержаться в правильной строке, например  aaabbbccc
а вот цепочка содержащая подцепочку ac не принадлежит языку

Но, вообще говоря, интересует любая информация в т.ч. и по разным частным случаям.

Это уже гораздо сложнее. Смутно вырисовывается алгоритм с "обратным" автоматом и описанием всех допустимых состояний... Но это все как-то неубедительно. И годится не для всех случаев. Боюсь, для каждой конкретной грамматики придется придумывать отдельный алгоритм.

Если не секрет, откуда взялась такая странная задача?

Да, общий метод тут особо не придумаешь, надо как минимум выделять классы грамматик и т.п.

А исходная задача такая: есть несколько служебных форматов файлов, для которых было бы очень здорово научиться собирать "разбитые" файлы, т.е. есть кусок памяти, надо найти в нем кусочки нашего файла и склеить их. Если формат представить какой-нибудь грамматикой вроде:

файл --> заголовок, тело, конец.
заголовок --> 0x1234, 0x5678, номер_версии.
ну и т.д.

то файл, можно воспринимать как цепочку, а задача определения "нашего кусочка" перерастает в то, что озвучено.
Реальная задача, конечно, существенно более простая в силу разных особенностей. Но перед тем как решать задачу в лоб, хотелось бы посмотреть, что по этому поводу думает теория, может подчерпнуть идеи. Да и сформулированная в абстрактном виде проблема, мне показалось интересной.

Очень похоже на задачу множественного поиска подстроки в строках. Но в этой задаче подстрока ищется в однозначно определённых строках (из них составляется бор, в нём строятся суффиксные ссылки - алгоритм Ахо-Корасик), а здесь же, похоже, постоянно возникают неопределённости...

Спасибо, почитаю на досуге что это за алгоритм Ахо-Корасика, может что в голову еще прийдет.

Блин, запутался я немножко. Алгоритм Ахо-Корасик ищет сразу несколько слов в качестве подстроки какой-то одной строки. Т.е. строки словаря в данном тексте. А у нас задача обратная... Так что это не подойдет