正規式是正規表達式，它是一種表示正規集的工具。 而且一個正規式它是對應于一個正規文法的。正規文法是3型文法。既然一個正規式對應一個正規文法，那麼它們之間肯定是能夠進行轉換的。從正規文法轉向正規式。規則2:A->xA|y有一個遞歸,遞歸展現在A->xA
三個規則涵蓋了所有的情況,不是說一個式子裡面套用一個規則就行了，規則隻是最簡單最基本的一種形式，然後呢到具體的文法當中就可能用到規則的組合了。
S->xSx|y與規則2非常類似，與規則2不同的是後面多了一個x。那樣就要靈活應用規則2.把式子拆開。一個式子是S->xS|y,S->xS|y可以得到x*y.另外一個式子
是S->Sx|y,S->Sx|y可以得到yx*.把x*y和yx*合并之後可以得到x*yx*.n>=0,x可以從0個到n個。n=0,S=y,就是S直接推導出y。
正規式表達的串是具有什麼特征的串。①②③三個串的共同特征都是以b結尾。(aa*|ab)*b這種串要麼是若幹個a,要麼是ab組成的。而且ab和若幹個a可以交替出現。如果說出現一個b，前面必須有一個a。不可能一眼把所有正規式的特征分析出來。在考場上分析出正規式的一部分特征就可以解題了。①的特征是任何一個b之前肯定有一個a。②(a|b)*②描述的是由a和b組成的若幹長度的串。①有限制,任何一個b之前有一個a。而②沒有這種限制。①②③都是把*b劃開來看，因為*b是相同的部分。③的特色是它涵蓋了②。③是((a|b)*|aa)*b,也就是說③可以看成是((a|b)*)*b,就是任意長度的由a和b組成的串。|不是必要組成部分,是以②和③除了末尾是b以外，前面是若幹個a和b組成的串。這種正規式題目沒有固定的規律可循，了解|和*它們的規則，然後呢進行靈活處理。看這種正規式能夠描述什麼樣的串來進行解題。