我使用符號L(a)來表示一種語言 - 一組字串，由正則運算式描述s。例如L(a)是 set {"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)*怎樣的？定義*為：
從s派生的任意數量（包括 0）字串的串聯 。數量取決于使用第二條規則的次數：
s* equals s* =>
s* => s(s*)
摘自Springer，編譯器設計簡介，2nd - 1.1 正則運算式
uj5u.com熱心網友回復：
我不認為你的例子是正確的（也許有錯字）。您需要的 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/316086.html
標籤：正则表达式