0
$\begingroup$

I'm just wondering if there is an algorithm to efficiently check if the language of one regular expression exists as substrings in the language of another regular expression.

The set of all strings that can be accepted (or matched) by a regular expression is the language of the regular expression.

for instance: I have two regular expressions, regex_1 = a+ab, regex_2 = xa+xaby, so language L_1 = {a, ab} and L_2 = {xa,xaby}.

We can tell that all strings in L1 are all substrings of strings in L2. All strings of the language of regex_1 should have the same "start point" as substrings in the language of regex_2 so that the behavior is performed as a whole. in this example, strings of L_1, both "a" and "ab", are all directly after "x" in L_2.

But in practice, there might be loops, and it might not be possible to simulate all traces to compare traces directly. So I wonder, how to decide in this situation.

Thanks.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It's still not entirely clear to me what "are all substrings of strings" means. Do you mean, for every string $x \in L_1$, there exists $y \in L_2$ such that $x$ is a substring of $y$? Also I don't know how to interpret the "same start point" or "behavior aspect" stuff. Perhaps you mean to check whether there exists a string $s$ such that for every $x \in L_1$, there exists some $y \in L_2$ and some string $t$ such that $y=sxt$? The first step is to figure out how to precisely articulate the problem statement that you are trying to solve. $\endgroup$
    – D.W. ♦
    Commented Oct 4 at 22:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.