正規式

其上的正規式及其表示的正規集可以遞歸定義如下。

① ε是一個正規式，它表示集合L(ε)={ε}。

② 若a是∑上的字符，則a是一個正規式，它所表示的正規集L(a)={a}。

③ 若正規式r和s分別表示正規集L(r)、L(s)，則

（a）r|s是正規式，表示集合L(r)∪L(s)；

（b）r·s是正規式，表示集合L(r)L(s)；

（c）r*是正規式，表示集合(L(r))*；

（d）(r)是正規式，表示集合L(r)。

僅由有限次地使用上述三個步驟定義的表達式才是∑上的正規式。

運算符“|”、“·”、“*”分別稱為“或”、“連接”和“閉包”。在正規式的書寫中，連接運算符“·”可省略。運算符的優先級從高到低順序排列為：“*”、“·”、“|”。

運算符“|”表示“或”、並集。“*”表示*之前括號裏的內容出現0次或多次。

若兩個正規式表示的正規集相同，則認為二者等價。兩個等價的正規集U和V記作U=V。

b(ab)*=(ba)*b,(a|b)*=(a*b*)*

需要注意的是，編譯原理裏面的正規式叫做範式，和正則表達式不是一個概念，但是有相通之處：都是通過一定的語法規則來描述文法，也就是所謂的匹配。