在 Coq 中制作和比较集合

Question

我无法理解是否有可能证明两组（在本例中为常规语言）是相同的，因此可以互换。据我了解，集合可以是等价的，即使它们在构造上不相等。

常规语言是字符串集，但我不知道如何说 r1 = r2 以便可以在证明中使用对称性之类的东西。

这是我的 RegularLanguage 声明：

Inductive RegularLanguage (A : Set) : Set :=
  | EmptyLang : RegularLanguage A
  | EmptyStr : RegularLanguage A
  | Unit : A -> RegularLanguage A
  | Union :
    RegularLanguage A
    -> RegularLanguage A
    -> RegularLanguage A
  | Concat :
    RegularLanguage A
    -> RegularLanguage A
    -> RegularLanguage A
  | KleeneStar : RegularLanguage A -> RegularLanguage A
.

尽管我说类型是 Set，但据我所知，这不会创建一组字符串。我需要一些 RegularLanguage -> Set of strings 类型的函数吗？

感谢您的帮助。

Answer 1

集合 RegularLanguage A 中的两个不同元素如果由不同的构造函数构造，则它们不相等。考虑 L1 = ( a | b ) 和 L2 = ( b | a)。这里 L1 <> L2 因为构造函数的参数不同。

在你的符号中，L1 可能是 Union nat (Unit nat 1) (Unit nat 2))，L2 是 Union nat (Unit nat 2) (Unit nat 1))。

相反，您想说有一个函数 regexp_match : A -> RegularLanguage A -> list A -> bool 可以匹配给定语言中的字符串。您将必须实现此功能。

如果两个正则表达式匹配并拒绝相同的字符串，则它们相等。例如，对于 L1 和 L2：

Lemma L1_eq_L2 : forall S, regexp_match L1 S = regexp_match L2 S.

如果你能证明这一点，那么你可以用它来将 regexp_match L1 S 替换为 regexp_match L2 S，反之亦然。

Answer 2

对于一些 Coq 概念存在一些误解，我将尝试澄清这些误解。

首先，在 Coq 中，您不应该将 Set 视为我们在传统数学中所说的 "set"。相反，您应该将其视为类型。 Coq 也有 Type，但出于这个 post 的目的，您可以将 Set 和 Type 视为可以互换。为了避免混淆，从现在开始，我将用"set"来指代传统数学中常用的集合概念，用"type"来指代Set和Type中的元素。在 Coq.

那么，集合和类型之间到底有什么区别？好吧，在普通数学中，问自己 anything 是否是 any 给定集合的成员是有意义的。因此，如果我们要在普通数学中发展正则表达式理论，并且将每个正则表达式视为一个集合，那么提出诸如 0 \in EmptyLang 之类的问题将是有意义的，因为，即使 0是一个自然数，它可以是任意集合先验的元素。作为一个不那么做作的例子，空字符串既是完整语言（即包含所有字符串的语言）的成员，也是任何基本语言的 Kleene 闭包的成员。

另一方面，在 Coq 中，语言的每个有效元素恰好有一个类型。例如，对于某些 A，空字符串的类型为 list A，写为 [] : list A。如果我们尝试使用 "has type" 语法询问 [] 是否属于某种常规语言，我们会得到一个错误；尝试输入例如

Check ([] : EmptyLang).

集合和类型都可以看作是元素的collections，但是类型在某种意义上限制性更强：比如可以取两个集合的交集，但是没有办法取交集两种类型。

二、写的时候

Inductive RegularLanguage (A : Set) : Set := (* ... *)

这 而不是 意味着您在 header 下面列出的元素定义集和类型。这意味着，对于每个类型 A（(A : Set) 部分），您正在定义一个新类型 RegularLanguage A（RegularLanguage (A : Set) : Set 部分），其元素是 由给定的构造函数列表自由生成。因此，我们有

EmptyLang : RegularLanguage nat

RegularLanguage nat : Set

但我们没有

EmptyLang : Set

（再一次，您可以尝试将上述所有判断输入 Coq 以查看哪些被接受，哪些不被接受）。

"freely generated" 尤其意味着您列出的构造函数是单射和 不相交。正如 larsr 之前指出的，特别是 Union l1 l2 = Union l2 l1 并非如此；事实上，你通常能够证明 Union l1 l2 <> Union l2 l1。问题在于，您在 Coq 中获得的归纳定义类型的相等性概念（您无法更改）与您预期的常规语言相等性概念之间存在不匹配。

虽然有几种解决方法，但我认为最简单的方法是使用 setoid rewrite 功能。这将涉及首先定义一个函数或谓词（例如，如 larsr 所建议的，布尔函数 regexp_match : RegularLanguage A -> list A -> bool）以确定常规语言何时包含某些字符串。然后，您可以定义语言的等价关系：

Definition regexp_equiv A (l1 l2 : RegularLanguage A) : Prop :=
  forall s, regexp_match l1 s = regexp_match l2 s.

并用setoid rewrite 来重写这个等价关系。然而，有一个小警告，那就是你只能在与这个等价关系兼容的上下文中用等价关系重写，并且你需要明确地证明引理才能这样做。您可以在 reference manual.

中找到更多详细信息

在 Coq 中制作和比较集合

Making and comparing Sets in Coq

set

equality

coq