作用代数（作用代数）

作用代数的概念

不像程序的动态逻辑和其他模态逻辑，对于它们程序和命题形成了两个不同的类别，作用代数合并了二者为一个单一类别。它可被认为是变异的直觉逻辑，带有星号并带有非交换性的合取，它的单位元不需要是顶元素。不像克莱尼代数，作用代数形成了一个簇，它进一步的是可有限公理化的，至关重要的公理是a·(a→a)* ≤a。不像克莱尼代数的等式理论的模型(正则表达式等式)，作用代数的星号运算是在所有等式的模型中自反传递闭包。

作用代数 (A, ∨, 0, ·, 1, ←, →, *) 是代数结构使得 (A, ∨, ·, 1, ←, →) 形成剩余半格而 (A, ∨, 0, ·, 1, *) 形成克莱尼代数。就是说，它是接合这两类代数理论的任何模型。克莱尼代数是用准等式公理化的，就是说，暗含在两个或更多等式之间，在直接以这种方式公理化的时候作用代数也是如此。使作用代数有特殊价值的是它们有等价的纯粹等式公理化。

在后面我们写不等式a≤b作为等式a∨b=b的简写。这允许我们使用不等式公理化理论而在不等式展开为等式的时候仍有纯粹等式公理化。

等式公理化

等式公理化的作用代数是剩余半格，加上下列对于星号的等式。

1 ∨a*·a* ∨a≤a*

a* ≤ (a∨b)*

(a→a)* ≤a→a 第一个等式可分解为三个等式 1 ≤a*,a*·a* ≤a* 和a≤a*。它们分别迫使a* 是自反的、传递的、并大于等于a。第二个公理断言星号是单调的。第三个公理可以等价的写为a·(a→a)* ≤a，这是使它的归纳角色更加明显的形式。这两个公理联合上剩余半格的公理迫使a* 是大于等于a的最小的自反的传递的半格元素。选取其为a的自反传递闭包的定义，也就是对于任何作用代数的所有元素a，a* 是a的自反传递闭包。

作用代数的无星号片段的等式理论中，这些不包含星号的等式，可以证明是相符于克莱尼代数的等式理论，也叫做正则表达式等式。在上述公理构成正则表达式的有限公理化的意义上。Redko 在 1967 年证明了这些等式没有有限公理化，约翰·何顿·康威在 1971 年对此给出更短的证明。Salomaa 给出了公理化这个理论的等式模式，Kozen 随后使用准等式或在等式间的蕴涵重新公式化它为有限公理化，至关重要的准等式是归纳的: 如果x·a≤x则x·a* ≤x，和如果a·x≤x则a*·x≤x。 Kozen 定义克莱尼代数是这种有限公理化的任何模型。

Conway 证明了正则表达式的等式理论允许其中a* 不是a的自反传递闭包的模型，通过给出一个四元素模型 0 ≤ 1 ≤a≤a* 其中a·a=a。在 Conway 的模型中，a是自反和传递的，因此它的自反传递闭包应该是a。但是正则表达式不确保如此，它允许a* 严格大于a。这种反常行为在作用代数中是不可能的。

相关概念

Kleene 星号

Kleene 闭包

如果V是M的子集，则V* 被定义为包含 ε(空字符串)并闭合于这个运算下的V的最小超集。接着V* 自身是幺半群，并被称为“V 生成的自由幺半群”。这是上面讨论的 Kleene 星号的推广，因为在某个符号的集合上所有字符串的集合形成了一个幺半群(带有字符串串接作为二元运算)。

1. 概述

（英语：Regular Expression、regex或regexp，缩写为RE），也译为

正规表示法

regex

2. 基本概念

一个正则表达式通常被称为一个模式 (pattern)，为用来描述或者匹配一系列符合某个句法规则的字符串。例如：Handel、Händel和Haendel这三个字符串，都可以由“H(a|ä|ae)ndel”这个模式来描述。大部分正则表达式的形式都有如下的结构：

选择

|

+

?

*

+

?

*

上述这些构造子都可以自由组合，因此，“H(ae?|ä)ndel”和“H(a|ae|ä)ndel”是相同的。

精确的语法可能因不同的工具或程序而异。

3. 形式化语言理论

正则表达式可以用形式化语言理论的方式来表达。正则表达式由常量和算子组成，它们分别指示字符串的集合和在这些集合上的运算。给定有限字母表 Σ 定义了下列常量:

(“空集”) ∅指示集合 ∅

(“空串”) ε 指示集合 {ε}

(“文字字符”) 在 Σ 中的a指示集合 {a}

定义了下列运算:

(“串接”)RS指示集合 { αβ | α ∈R∧ β ∈S}。例如 {"ab"|"c"}{"d"|"ef"} = {"abd", "abef", "cd", "cef"}。

(“选择”)R|S指示R和S的并集。

(“Kleene星号”)R* 指示包含 ε 并且闭包在字符串串接下的R的最小超集。这是可以通过R中的零或多个字符串的串接得到所有字符串的集合。例如，{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }。

上述常量和算子形成了克莱尼代数。

很多课本使用对选择使用符号 ∪, +或 ∨替代竖杠。

为了避免括号，假定 Kleene 星号有最高优先级，接着是串接，接着是并集。如果没有歧义则可以省略括号。例如，(ab)c可以写为 abc而 a|(b(c*))可以写为 a|bc*。

例子

任何Heyting代数(因此任何布尔代数)通过选取 · 为 ∧ 和a* = 1 就得到了一个作用代数。这对于星号是必要和充分的，因为 Heyting 代数的顶元素 1 是它的唯一自反元素，并且是传递的，还大于等于这个代数的所有元素。

在字母表 Σ 上所有形式语言(有限字符串的集合)的集合 2 形成了一个作用代数，带有 0 为空集，1 = {ε}，∨ 为并集，· 为串接，L←M为所有字符串x使得xM⊆L的集合(对偶于M→L)，而L* 是在L中字符串形成的所有字符串的集合(Kleene闭包)。

在集合X上的所有二元关系的集合 形成一个作用代数，带有 0 为空关系，1 为恒等关系或等式，∨ 为并集，· 为关系复合，R←S为所有有序对 (x,y) 使得对于所有X中的z有ySz蕴涵xRz所构成的关系(对偶于S→R)，和R*为R的自反传递闭包，定义为在所有关系R对整数n≥ 0 的并集。