ชุดปกติ
ชุดใด ๆ ที่แสดงถึงค่าของนิพจน์ทั่วไปเรียกว่า a Regular Set.
คุณสมบัติของชุดปกติ
Property 1. การรวมกันของชุดปกติสองชุดเป็นเรื่องปกติ
Proof -
ให้เราใช้สองนิพจน์ทั่วไป
RE 1 = a (aa) * และ RE 2 = (aa) *
ดังนั้นL 1 = {a, aaa, aaaaa, ..... } (สตริงที่มีความยาวคี่ไม่รวม Null)
และ L 2 = {ε, aa, aaaa, aaaaaa, ....... } (สตริงที่มีความยาวสม่ำเสมอรวมทั้ง Null)
L 1 ∪ L 2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, ....... }
(สตริงของความยาวที่เป็นไปได้ทั้งหมดรวมทั้ง Null)
RE (L 1 ∪ L 2 ) = a * (ซึ่งเป็นนิพจน์ทั่วไป)
Hence, proved.
Property 2. จุดตัดของสองชุดปกติเป็นประจำ
Proof -
ให้เราใช้สองนิพจน์ทั่วไป
RE 1 = a (a *) และ RE 2 = (aa) *
ดังนั้นL 1 = {a, aa, aaa, aaaa, .... } (สตริงของความยาวที่เป็นไปได้ทั้งหมดยกเว้น Null)
L 2 = {ε, aa, aaaa, aaaaaa, ....... } (สตริงที่มีความยาวเท่ากันรวมทั้ง Null)
L 1 ∩ L 2 = {aa, aaaa, aaaaaa, ....... } (สตริงที่มีความยาวเท่ากันไม่รวม Null)
RE (L 1 ∩ L 2 ) = aa (aa) * ซึ่งเป็นนิพจน์ทั่วไป
Hence, proved.
Property 3. ส่วนเสริมของชุดปกติเป็นแบบปกติ
Proof -
ให้เราใช้นิพจน์ทั่วไป -
RE = (aa) *
ดังนั้นL = {ε, aa, aaaa, aaaaaa, ....... } (สตริงที่มีความยาวเท่ากันรวมทั้ง Null)
ส่วนเสริมของ L คือสตริงทั้งหมดที่ไม่อยู่ใน L.
ดังนั้นL '= {a, aaa, aaaaa, ..... } (สตริงที่มีความยาวคี่ไม่รวม Null)
RE (L ') = a (aa) * ซึ่งเป็นนิพจน์ทั่วไป
Hence, proved.
Property 4. ความแตกต่างของชุดปกติสองชุดเป็นเรื่องปกติ
Proof -
ให้เราใช้สองนิพจน์ทั่วไป -
RE 1 = a (a *) และ RE 2 = (aa) *
ดังนั้นL 1 = {a, aa, aaa, aaaa, .... } (สตริงของความยาวที่เป็นไปได้ทั้งหมดไม่รวม Null)
L 2 = {ε, aa, aaaa, aaaaaa, ....... } (สตริงที่มีความยาวเท่ากันรวมทั้ง Null)
ล1 - ล2 = {ก, aaa, aaaaa, aaaaaaa, .... }
(สตริงของความยาวคี่ทั้งหมดไม่รวมค่า Null)
RE (L 1 - L 2 ) = a (aa) * ซึ่งเป็นนิพจน์ทั่วไป
Hence, proved.
Property 5. การกลับตัวของชุดปกติเป็นเรื่องปกติ
Proof -
เราต้องพิสูจน์ LR เป็นเรื่องปกติถ้า L เป็นชุดปกติ
ให้L = {01, 10, 11, 10}
RE (L) = 01 + 10 + 11 + 10
L R = {10, 01, 11, 01}
RE (L R ) = 01 + 10 + 11 + 10 ซึ่งเป็นปกติ
Hence, proved.
Property 6. การปิดชุดปกติเป็นเรื่องปกติ
Proof -
ถ้า L = {a, aaa, aaaaa, ....... } (สตริงที่มีความยาวคี่ไม่รวม Null)
กล่าวคือRE (L) = a (aa) *
L * = {a, aa, aaa, aaaa, aaaaa, ……………} (สตริงของความยาวทั้งหมดไม่รวม Null)
RE (L *) = a (ก) *
Hence, proved.
Property 7. การต่อกันของชุดปกติสองชุดเป็นเรื่องปกติ
Proof −
ให้RE 1 = (0 + 1) * 0 และ RE 2 = 01 (0 + 1) *
ที่นี่L 1 = {0, 00, 10,000, 010, ...... } (ชุดของสตริงที่ลงท้ายด้วย 0)
และL 2 = {01, 010,011, ..... } (ชุดของสตริงที่ขึ้นต้นด้วย 01)
จากนั้นL 1 L 2 = {001,0010,0011,0001,00010,00011,1001,10010, ............. }
ชุดของสตริงที่มี 001 เป็นสตริงย่อยซึ่งแทนได้ด้วย RE - (0 + 1) * 001 (0 + 1) *
ดังนั้นพิสูจน์แล้ว
ข้อมูลประจำตัวที่เกี่ยวข้องกับนิพจน์ทั่วไป
กำหนดให้ R, P, L, Q เป็นนิพจน์ทั่วไปอัตลักษณ์ต่อไปนี้ถือ -
- ∅ * = ε
- ε * = ε
- RR * = R * R
- R * R * = R *
- (R *) * = R *
- RR * = R * R
- (PQ) * P = P (QP) *
- (a + b) * = (a * b *) * = (a * + b *) * = (a + b *) * = a * (ba *) *
- R + ∅ = ∅ + R = R (ตัวตนสำหรับสหภาพ)
- R ε = ε R = R (ข้อมูลประจำตัวสำหรับการเรียงต่อกัน)
- ∅ L = L ∅ = ∅ (ตัวทำลายสำหรับการต่อกัน)
- R + R = R (กฎหมายกำหนดอำนาจ)
- L (M + N) = LM + LN (กฎหมายการกระจายด้านซ้าย)
- (M + N) L = ML + NL (กฎหมายการกระจายสิทธิ์)
- ε + RR * = ε + R * R = R *