通过派生规则查找正则表达式的语言

Question

我使用符号L(a)来表示语言-一组字符串，由正则表达式s描述。例如，L(a)为集{"a"}。

同样，使用派生规则查找正则表达式的语言，我可以做以下事情:

L(a(b|c)) => {ab, ac}

因为

a(b|c) => a(b) = ab

和

a(b|c) => a(c) = ac

我能理解。但是我想不出下面这个例子中的派生:

L((a|b)*) = ab

因为

(a|b)*
=> (a|b)(a|b)*
=> a(a|b)*
=> a(a|b)(a|b)*
=> ab(a|b)*
=> ab

为什么第一步是(a|b)(a|b)*?将*定义为:

派生的任意数目(包括0)的串接。这个数字取决于第二个规则被使用了多少次:

s*        equals   s* =>
s* => s(s*)

摘自Springer, Introduction to Compiler Design, 2nd - 1.1正则表达式

Answer 1

我不认为你的例子是正确的(也许有一个打字错误)。您需要的Brzozowski的推导规则是:

(1) L(a*)  = L(a)*
(2) L(a|b) = L(a) U L(b)
(3) L(a)   = {a}

则得到:

L((a|b)*) = L(a|b)*         ; applying rule #1, note the Kleene star location
= (L(a) U L(b))*  ; rule #2
= ({a} U {b})*    ; rule #3, two times
= ({a, b})*       ; combining into a single set
= {a, b}*         ; removing the useless parentheses