นิพจน์ทั่วไป

ก Regular Expression สามารถกำหนดซ้ำได้ดังนี้ -

• ε เป็นนิพจน์ทั่วไประบุภาษาที่มีสตริงว่าง (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 กฎนั้นจะเป็นนิพจน์ทั่วไป

ตัวอย่าง RE บางส่วน

นิพจน์ทั่วไป	ชุดปกติ
(0 + 10 *)	L = {0, 1, 10, 100, 1000, 10000, …}
(0 * 10 *)	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	ชุดสตริงของ a และ b ที่ลงท้ายด้วยสตริง abb ดังนั้น L = {abb, aabb, babb, aaabb, ababb, ………… .. }
(11) *	ชุดประกอบด้วยเลขคู่ของ 1 รวมสตริงว่างดังนั้น L = {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * ข	ชุดของสตริงประกอบด้วยจำนวนคู่ของ a ตามด้วยจำนวนคี่ของ b ดังนั้น L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… .. }
(aa + ab + ba + bb) *	สตริงของ a และ b ที่มีความยาวเท่ากันสามารถหาได้โดยการรวมสตริง aa, ab, ba และ bb รวมทั้ง null ดังนั้น L = {aa, ab, ba, bb, aaab, aaba, ………… .. }