簡介
其上的正規式及其表示的正規集可以遞歸定義如下。
① ε是一個正規式，它表示集合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*)*
需要注意的是，編譯原理裡面的正規式叫做範式，和正則表達式不是一個概念，但是有相通之處：都是通過一定的語法規則來描述文法，也就是所謂的匹配。
