正則表示式

正則表示式將形式語言定義為有限字母表上的字串集合。令 表示一個選定的字母表。那麼 是一個正則表示式，表示空集，而 是一個正則表示式，表示包含空字串作為其唯一元素的集合。

如果 , 那麼 是一個正則表示式，表示僅包含字串 的集合。如果 和 是正則表示式，分別表示集合 和 ，那麼

1. 是一個正則表示式，表示集合 ，其中 表示並集。

2. 是一個正則表示式，表示所有字串 和 的連線所形成的集合，其中 且 。

3. 是一個正則表示式，表示 的閉包，即由 中的字串進行零次或多次連線所形成的集合。

由正則表示式定義的集合稱為正則集，一個集合是正則的當且僅當它由右線性文法定義。