Z3能否找到满足一些例子的正则表达式？

Question

我有一组这样的字符串：

{"01", "001", 000111", 01111"}

现在，我想知道我是否可以要求 Microsoft Z3 找到满足字符串的最小正则表达式。例如，这个特定集合的输出应该类似于 0*1*.

Answer 1

理论上是的。实际上，是的，但可能不是您想要的方式。至少，现在还没有。

严格来说，编写您想要的代码很容易。以下是您如何为您想要的集合编写问题代码：

(set-logic QF_S)
(set-option :produce-models true)

(define-fun re1 () RegLan (str.to_re "01"))
(define-fun re2 () RegLan (str.to_re "001"))
(define-fun re3 () RegLan (str.to_re "000111"))
(define-fun re4 () RegLan (str.to_re "01111"))
(define-fun re5 () RegLan (re.union re1 re2 re3 re4))
(check-sat)
(get-value (re5))

事实上，z3 说：

sat
((re5 (re.union (str.to_re "01")
          (re.union (str.to_re "001")
                    (re.union (str.to_re "000111") (str.to_re "01111"))))))

但我能听到你呻吟着说“但这不是我想要的！”事实上，虽然这个是一个正确的解决方案，但它可能不是您想要的。它绝不是任何令人满意的意义上的“最小”。

要真正做到您所需要的，您希望能够写下可以代表正则表达式本身的变量。事实上，SMTLib 和 z3 允许正则表达式是符号的。详情请见此处：https://smtlib.cs.uiowa.edu/theories-UnicodeStrings.shtml。但是，这里是该页面中关于允许使用哪种正则表达式的直接引述：

Function str.to_re allows one to write symbolic regular expressions, e.g., RegLan terms with subterms like (str.to_re x) where x is a variable. Such terms have more expressive power than regular expressions. This is intentional, for future developments. The restriction to actual regular expressions will be imposed in a logic where str.to_re will be applicable to string constants only.

据我所知，目前还没有支持符号正则表达式的 SMT 求解器，包括 z3。这是一个简单的实验：

(set-logic QF_S)
(declare-fun x () RegLan)
(assert (str.in_re "0" x))
(check-sat)

当我将其提供给 z3 时，我得到：

unknown

也就是说，这是一个有效的问题，但 z3 无法处理它。如果你把它喂给cvc4，它会更直言不讳地谈论这个问题：

(error "Regular expression variables are not supported.")

因此，总结一下：您尝试做的事情在 SMTLib 中是可能的，但目前没有任何求解器支持它，至少不是您希望它工作的方式。希望这在未来可能会改变，尽管我不会屏住呼吸。

鉴于此，你能做什么？我认为为此使用 SMT 求解器有点矫枉过正。对于每个常量字符串，您可以构造识别它的正则表达式。把它变成一个 DFA。然后采用所有这些 DFA 的联合。最后，将它变成一个最小的 DFA，并读出它的正则表达式。这是相当多的工作，但在实践中应该运作良好，即这个策略的所有部分都是众所周知的如何实现，并且在运行时间复杂度方面应该相当便宜。

Z3能否找到满足一些例子的正则表达式？

Can Z3 find a regular expression that satisfies some examples?

regex

z3