正則表示式

正則表示式可以遞迴地定義如下：

ε 是一個正則表示式，表示包含空字串的語言。(L (ε) = {ε})
φ 是一個正則表示式，表示空語言。(L (φ) = { })
x 是一個正則表示式，其中 L = {x}
如果X是一個表示語言L(X)的正則表示式，並且Y是一個表示語言L(Y)的正則表示式，則
- X + Y 是一個對應於語言L(X) ∪ L(Y)的正則表示式，其中L(X+Y) = L(X) ∪ L(Y)。
- X . Y 是一個對應於語言L(X) . L(Y)的正則表示式，其中L(X.Y) = L(X) . L(Y)
- R* 是一個對應於語言L(R*)的正則表示式，其中L(R*) = (L(R))*
如果我們從 1 到 5 多次應用任何規則，它們都是正則表示式。

一些正則表示式示例

正則表示式	正則集
(0 + 10*)	L = { 0, 1, 10, 100, 1000, 10000, … }
(010)	L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε)	L = {ε, 0, 1, 01}
(a+b)*	任意長度的 a 和 b 字串的集合，包括空字串。所以 L = { ε, a, b, aa , ab , bb , ba, aaa…….}
(a+b)*abb	以字串 abb 結尾的 a 和 b 字串的集合。所以 L = {abb, aabb, babb, aaabb, ababb, …………..}
(11)*	包含偶數個 1 的字串集合，包括空字串，所以 L= {ε, 11, 1111, 111111, ……….}
(aa)(bb)b	由偶數個 a 後跟奇數個 b 組成的字串集合，所以 L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, …………..}
(aa + ab + ba + bb)*	偶數長度的 a 和 b 字串可以透過連線 aa、ab、ba 和 bb 的任意組合（包括空字串）獲得，所以 L = {aa, ab, ba, bb, aaab, aaba, …………..}

列印頁面

廣告