6
$\begingroup$

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?

Example

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 : '</title "]]>"'.

Motivation

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.

$\endgroup$
  • $\begingroup$ "such that (a b) is a prefix of a string in (A B)" -- (a b) is trivially a prefix of itself; do you mean proper prefix? $\endgroup$ – Raphael Mar 28 '13 at 10:20
4
$\begingroup$

If I translate your description properly, here is what you want to ask:

Given two regular language $A$, $B$, is there a 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$?

Formally:

Given regular $A$ and $B$, are there $a = wx \in A$ and $b = yz \in B$ so that $xy \in B$?

Deciding this boils down to deciding whether

$\qquad B \cap (\operatorname{suff}(A) \cdot \operatorname{pref}(B) ) = \emptyset$.

Now we employ some closure properties: $\mathrm{REG}$ is closed against right and left quotient, concatenation and intersection, so with

$\qquad \operatorname{suff}(A) = A \backslash \Sigma^*$ and $\operatorname{pref}(B) = B / \Sigma^*$

the set we want to check for emptiness is regular, and therefore the check is indeed decidable.

In order to actually do this, I suggest you build automata for $\operatorname{suff}(A)$ and $\operatorname{pref}(B)$, concatenate them, intersect the result with the automaton for $B$ and use the standard check for emptiness (is a final state reachable from the initial state?).

Note that you never need DFA, all of this works nicely with NFA. Therefore, no exponential state explosion occurs; intersection multiplies the state numbers, though.

$\endgroup$
  • $\begingroup$ Your English phrasing of my problem sounds right. Thanks for wading through my gibberish. $\endgroup$ – Mike Samuel Mar 28 '13 at 18:42
2
$\begingroup$

DFA intersection is a solved problem - given two DFAs (or NFAs, or regular grammars), we can come up with a DFA for the intersection of the two languages accepted by these DFAs. Also, it is known how to check whether the language accepted by a DFA is empty or not. Other closure properties are listed in the Wikipedia article.

Your problem is most probably solvable by using "constructive closure properties" (like intersection and concatenation), and the test for emptiness. In this sense, it is a solved problem. I don't know whether it appears anywhere.

$\endgroup$
  • $\begingroup$ Is it fairly straightforward to go from a DFA for a language L to a DFA for all substrings of strings in L and to a DFA for all suffixes of strings in L without a state explosion? I suppose the first involves adding an edge from the start to every other state and from every state to the terminus, and the latter involves just the first part of that transform? $\endgroup$ – Mike Samuel Mar 28 '13 at 0:31
  • 1
    $\begingroup$ It is either straightforward or impossible. In this case, it's straightforward. For prefixes, for example, it's enough to determine which states are not "error states", and make them accepting. $\endgroup$ – Yuval Filmus Mar 28 '13 at 2:26
  • $\begingroup$ For suffixes, it's impossible. Consider the language $L = \{ \alpha w : \alpha \notin w \}$, where $\alpha$ is a symbol. For an alphabet of size $m$, the smallest DFA has size $m+1$, but the smallest DFA for the suffix language has exponential size. $\endgroup$ – Yuval Filmus Mar 28 '13 at 2:30
  • 1
    $\begingroup$ Hmm. Since substrings include both prefixes and suffixes, reversal of the language won't help. $\endgroup$ – Mike Samuel Mar 28 '13 at 3:02
  • $\begingroup$ Since this is a compiler optimization, I'll probably just have to go heuristic -- find a required element in B that cannot match a substring of A, "<" in the top example. $\endgroup$ – Mike Samuel Mar 28 '13 at 3:03
0
$\begingroup$

Assume DFAs given, it is easier. And get rid of useless states, and kill off any dead states.

To get a DFA for the language of all prefixes of $A$ is easy: Make all states final.

Then you can compute the intersection between that and $B$, and you have the set of $B$s that are prefixes of $A$s.

No idea what it might be called. The algorithm cited is just a proof of concept idea.

$\endgroup$
  • $\begingroup$ I don't think what I want is the Bs that are prefixes of As. I edited my question to try to phrase it as an intersection problem. $\endgroup$ – Mike Samuel Mar 27 '13 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.