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

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

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

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

извините за очепятки

AlexandrPlus , правильно ли я понял, что Вы предлагаете попытаться дополнить цепочку до полной путем добавления в начало и конец нетерминальных символов, а уже потом эту цепочку (или вывод из нее) проверять обычным способом?

Примерно понятно, спасибо за ответ.