正则语言中判断子串可参与匹配的属性术语查询

问题背景与示例 #

给定正则表达式[^x]xyx[^x]：

• 它可匹配完整字符串abcxyxdef；
• 字符串abcx、yxdef、abc这类内容，能够与该正则的匹配片段产生交集（即它们是某个正则匹配结果的子串、前缀或后缀）；
• 但xxyx、xx这类字符串，完全不可能成为该正则任何匹配结果的一部分；
• 而xxyxaxy可以从其中的a字符位置开始匹配该正则。

判断逻辑的代码示例 #

通过DFA可实现上述“某字符串是否能与正则的匹配结果产生交集”的判断，核心逻辑的伪代码如下：

sketchdef possible(input, DFA): 
  # 场景1：从输入字符串的任意位置开始匹配正则
  for each character position in input
    walk the DFA from entry node with rest of input
    return true if we run out of input avoiding the reject node, 
    return true if we exited DFA
  # 场景2：输入字符串是正则匹配结果的后缀（即匹配起始于输入之前）
  for each node in DFA
    walk the DFA from that node with all of input
    return true if we run out of input avoiding the reject node, 
    return true if we exited DFA
  return false

需求 #

需确认：在语言理论、计算机科学（正则语言领域）的学术文献中，上述判断对应的属性是否存在标准术语；若不存在，则明确该结论。已检索谷歌及Sipser相关教材，未找到对应术语。

内容的提问来源于stack exchange，提问作者jojo hohanon