可空性(正则表达式)

Question

在Brzozowski的"正则表达式的导数"和其他地方,如果R可以为空,函数δ(R)返回λ,否则,包括如下条款:

?(R1 + R2) = ?(R1) + ?(R2)
?(R1 · R2) = ?(R1) ? ?(R2)

显然,如果R1和R2都可以为空,则(R1·R2)可以为空,如果R1或R2可以为空,那么(R1 + R2)可以为空.然而,我不清楚上述条款应该是什么意思.我的第一个想法,映射(+),(·)或布尔运算到常规集是没有意义的,因为在基本情况下,

?(a) = ? (for all a ? ?)
?(?) = ?
?(?) = ?

并且λ不是一个集合(也不是设置δ的返回类型,这是一个正则表达式).此外,没有指出这种映射,并且有一个单独的表示法.我理解可空性,但我对δ的定义中的和,乘积和布尔运算的定义感到迷失:例如,在定义中,λ或how是如何从δ(R1)∧δ(R2)返回的关δ(R1·R2)？

Answer 1

我认为你被作者所采取的符号自由所困扰。\xce\xb4(R) 的返回类型肯定是一个集合，或者更确切地说是一种语言。如果你看一下定义：

\n\n

\n\n

你可以看到返回类型不一致，形式上 \xce\xbb 是一个元素，但 \xe2\x88\x85 是空语言...应该说的是：

\n\n

\n\n

作者对空字符串以及仅包含空字符串的语言都使用 \xce\xbb ，这一事实由他对 Kleene 星运算符的定义进一步证明：

\n\n

\n\n

显然，最后一部分应该是如果我们想迂腐。

\n\n

考虑到 \xce\xb4(R) 的返回类型是一个集合，或者更确切地说是一种语言，您给出的方程非常有意义并且准确地表达了您所描述的内容。

\n