检查正则表达式是否不明确

Question

我想知道是否有一种方法可以自动检查正则表达式的歧义性。如果存在可以通过正则表达式中的多种方式匹配的字符串，则该正则表达式被视为不明确。例如，给定一个 regex R = (ab)*(a|b)*，我们可以检测到这R是一个不明确的正则表达式，因为有两种方法可以匹配ab来自 R 的字符串。

更新

问题是如何检查正则表达式的定义是否不明确。我知道在正则表达式机制的实际实现中，总是有一种方法来匹配正则表达式，但请以学术的方式阅读和思考这个问题。

Answer 1

当且仅当相应的格卢什科夫自动机不是确定性的时，正则表达式才是一模糊的。现在这可以在线性时间内完成。这是一个链接。顺便说一句，确定性正则表达式也以“一无歧义”的名义进行了研究。