正閉包

20世紀50年代，美國數學家斯蒂芬·科爾·克萊尼提出了正則表達式的三類基本運算：並、連接、克林閉包（又稱星閉包，Kleene星號）。此後學界發現很多時候需要描述一個語言連接1次或以上得到的集合，因此由克林閉包的概念衍生出了正閉包的概念。 ^[1] 

對於語言L，L的正閉包定義為：

^[1] 

1、冪等性：

2、結合性：正閉包具有左結合性。

3、優先級：正閉包和克林閉包一樣在正則表達式運算中具有最高優先級。

4、由克林閉包推出正閉包：

5、由正閉包推出克林閉包：

^{[1]  [2]} 

例：由a和b組成且不含有三個連續的b的字符串的正則表達式（All strings of a's and b's that contain no three consecutive b's）。

答案：

題目來源：《編譯原理與實踐》（英文版）第2章課後題2.1.f題 ^[2] 

解析：不含有三個連續的b意味着除了{b}和{bb}這兩種不含有a的情況外，每至多出現2個連續的b後必須出現至少1個a，因此構造出

，但這樣寫忽略了以b結尾的情況，因此要在後面連接

。這樣再並上b和bb，得到正解。