I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most match of B in (a b) includes one or more characters from a.
Raphael's formulation is good:
Given two regular language A, B, is there a (non-empty) prefix of a word b in B that is a suffix of a word in A so that the rest of b is a prefix of another word in B?
For example, let's say I have two regular languages, one which describes some properly escaped HTML text, and one which describes an end tag:
A := ([^&<>] | [&] [a-z] [a-z0-9]+ [;])*; B := "</title";
By inspection, I can tell that there is no string (a b) in (A B) such that the first match of B includes characters from a because
"<" is a prefix of B which cannot occur as a suffix of A.
But given a different grammar:
A' := (A | "<![CDATA[" ("]"? ">" | "]"* [^\]>])* "]]>")*; B' := "</title" ([^>\"] | [\"] [^\"]* [\"])* ">";
then there are strings
a = '<![CDATA[</title "]]>"'; b = '</title>';
where (A B) matches
'<![CDATA[</title "]]>"</title>' and the left-most match of B is
'</title "]]>"</title>' which includes a non-empty suffix of a :
A in my situation describes the output of an encoder/sanitizer that is derived from a grammar, so an untrusted input is fed to the encoder/sanitizer and I know the output matches A by construction.
B is a limit condition in a larger grammar that describes how parsers determine where a chunk of an embedded language ends so they can hand it off to a parser for the embedded language.
My end goal is to be able to determine when I can optimize away runtime checks that ensure that it is safe to embed a particular encoded string. For these examples, it would be safe to optimize out the first check, but not the second.
Is this a solved problem? Does it have a name? Any pointers appreciated.