ในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีและทฤษฎีภาษาเชิงรูปธรรมภาษาปกติ (เรียกอีกอย่างว่าภาษาเชิงเหตุผล ) ^{[ 1 ] [ 2 ]}คือภาษาเชิงรูปธรรมที่สามารถกำหนดได้ด้วยนิพจน์ปกติในความหมายที่เข้มงวดในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี (ตรงข้ามกับเครื่องมือนิพจน์ปกติสมัยใหม่จำนวนมาก ซึ่งได้รับการเสริมด้วยคุณสมบัติที่ช่วยให้สามารถรับรู้ภาษาที่ไม่ใช่ปกติได้)

อีกทางเลือกหนึ่ง ภาษาปกติสามารถนิยามได้ว่าเป็นภาษาที่ได้รับการยอมรับโดยออโตมาตาจำกัดความเท่าเทียมกันของนิพจน์ปกติและออโตมาตาจำกัดเป็นที่รู้จักกันในชื่อทฤษฎีบทของคลีน^{[ 3 ]} (ตั้งชื่อตามนักคณิตศาสตร์ชาวอเมริกันStephen Cole Kleene ) ในลำดับชั้นของ Chomskyภาษาปกติคือภาษาที่สร้างขึ้นโดยไวยากรณ์ประเภท 3

ชุดของภาษาปกติบนตัวอักษร Σ ถูกกำหนดแบบเวียนซ้ำดังนี้:

• ภาษาว่างเปล่า ∅ เป็นภาษาปกติ
• สำหรับแต่ละa ∈ Σ ( โดยที่ aเป็นสมาชิกของ Σ) ภาษาที่มีสมาชิกเดียว{ a }เป็นภาษาปกติ
• ถ้าAเป็นภาษาปกติA * ( Kleene star ) ก็จะเป็นภาษาปกติเช่นกัน ด้วยเหตุนี้ ภาษาของสตริงว่าง{ε}จึงเป็นภาษาปกติด้วย
• ถ้าAและBเป็นภาษาปกติแล้วA ∪ B (การรวมกัน) และA • B (การต่อกัน) ก็จะเป็นภาษาปกติเช่นกัน
• ไม่มีภาษาอื่นใดนอกเหนือจาก Σ ที่เป็นภาษาปกติ

ดูหัวข้อ นิพจน์ปกติ §  ทฤษฎีภาษาเชิงรูปธรรมสำหรับไวยากรณ์และความหมายของนิพจน์ปกติ

ภาษาจำกัดทั้งหมดเป็นภาษาปกติ โดยเฉพาะอย่างยิ่งภาษาสตริงว่าง{ε} = ∅*เป็นภาษาปกติ ตัวอย่างทั่วไปอื่นๆ ได้แก่ ภาษาที่ประกอบด้วยสตริงทั้งหมดบนตัวอักษร{ a , b }ซึ่งมีจำนวนa เป็น เลขคู่ หรือภาษาที่ประกอบด้วยสตริงทั้งหมดในรูปแบบ: a หลาย ตัวตามด้วยb หลาย ตัว

ตัวอย่างง่ายๆ ของภาษาที่ไม่ปกติคือเซตของสตริง{ a ⁿ b ⁿ | n ≥ 0} [ ^{4 ] ตาม}สัญชาตญาณแล้ว ไม่สามารถจดจำได้ด้วยออโตมาตอนจำกัด เนื่องจากออโตมาตอนจำกัดมีหน่วยความจำจำกัดและไม่สามารถจดจำจำนวน a ที่แน่นอนได้ เทคนิคในการพิสูจน์ข้อเท็จจริงนี้อย่างเข้มงวดมีดังต่อไปนี้

ภาษาปกติ (Regular language) มีคุณสมบัติเทียบเท่าดังต่อไปนี้:

1. มันคือภาษาของนิพจน์ปกติ (ตามคำนิยามข้างต้น)
2. เป็นภาษาที่ยอมรับโดยออโตมาตาจำกัดแบบไม่กำหนด (NFA) ^{[หมายเหตุ 1 ] [หมายเหตุ 2 ]}
3. เป็นภาษาที่ยอมรับโดยออโตมาตาจำกัดเชิงกำหนด (DFA) ^{[หมายเหตุ 3 ] [หมายเหตุ 4 ]}
4. สามารถสร้างได้โดยใช้ไวยากรณ์ปกติ^{[หมายเหตุ 5 ] [หมายเหตุ 6 ]}
5. เป็นภาษาที่ยอมรับโดยออโตมาตาจำกัดแบบสลับ
6. เป็นภาษาที่ยอมรับโดยออโตมาตาจำกัดแบบสองทาง
7. สามารถสร้างได้โดยใช้ไวยากรณ์คำนำหน้า
8. เครื่องจักรทัวริงแบบอ่านอย่างเดียวสามารถยอมรับได้
9. สามารถกำหนดได้ในตรรกะลำดับที่สองแบบเอกภาค ( ทฤษฎีบท Büchi–Elgot–Trakhtenbrot ) ^{[ 5 ]}
10. ได้รับการยอมรับโดยโมโนอิดเชิงไวยากรณ์ จำกัด M บางตัว หมายความว่าเป็นภาพก่อนหน้า{ w ∈ Σ ^* | f ( w ) ∈ S }ของเซตย่อยSของโมโนอิด จำกัด Mภายใต้โฮโมมอร์ฟิซึมโมโนอิดf  : Σ ^* → Mจากโมโนอิดอิสระบนตัวอักษรของมัน^{[หมายเหตุ 7 ]}
11. จำนวนชั้นสมมูลของความสอดคล้องทางไวยากรณ์ นั้น มีจำกัด^{[หมายเหตุ 8 ] [หมายเหตุ 9 ]} (จำนวนนี้เท่ากับจำนวนสถานะของออโตมาตาจำกัดเชิงกำหนดขั้นต่ำที่ยอมรับL )

คุณสมบัติข้อ 10 และ 11 เป็นวิธีการทางพีชคณิตล้วนๆ ในการกำหนดภาษาปกติ ชุดข้อความที่คล้ายกันนี้สามารถกำหนดขึ้นสำหรับโมโนอิดM ⊆ Σ ^*ได้เช่นกัน ในกรณีนี้ ความเท่าเทียมกันเหนือMนำไปสู่แนวคิดของภาษาที่สามารถจดจำได้

ผู้เขียนบางคนใช้คุณสมบัติข้อใดข้อหนึ่งข้างต้นที่แตกต่างจาก "1." เป็นคำจำกัดความทางเลือกของภาษาปกติ

ความเท่าเทียมกันบางส่วนข้างต้น โดยเฉพาะอย่างยิ่งระหว่างรูปแบบสี่แบบแรก เรียกว่าทฤษฎีบทของ Kleeneในตำราเรียน ชื่อที่ใช้เรียกทฤษฎีบทใด (หรือเซตย่อยใด) นั้นแตกต่างกันไปในแต่ละผู้เขียน ตำราเรียนเล่มหนึ่งเรียกความเท่าเทียมกันของนิพจน์ปกติและ NFA ("1." และ "2." ข้างต้น) ว่า "ทฤษฎีบทของ Kleene" ^{[ 6 ]}ตำราเรียนอีกเล่มหนึ่งเรียกความเท่าเทียมกันของนิพจน์ปกติและ DFA ("1." และ "3." ข้างต้น) ว่า "ทฤษฎีบทของ Kleene" ^{[ 7 ]}ตำราเรียนอีกสองเล่มพิสูจน์ความเท่าเทียมกันเชิงการแสดงออกของ NFA และ DFA ("2." และ "3.") ก่อน แล้วจึงระบุ "ทฤษฎีบทของ Kleene" ว่าเป็นความเท่าเทียมกันระหว่างนิพจน์ปกติและออโตมาตาจำกัด (ซึ่งกล่าวกันว่าอธิบาย "ภาษาที่สามารถจดจำได้") ^{[ 2 ] [ 8 ]}ข้อความที่เน้นด้านภาษาศาสตร์จะเทียบไวยากรณ์ปกติ ("4." ข้างต้น) กับ DFA และ NFA ก่อน จากนั้นเรียกภาษาที่สร้างขึ้นโดย (ใดๆ ของ) เหล่านี้ว่า "ปกติ" หลังจากนั้นจึงแนะนำนิพจน์ปกติซึ่งเรียกว่า "ภาษาเชิงเหตุผล" และสุดท้ายระบุ "ทฤษฎีบทของคลีน" ว่าเป็นความสอดคล้องกันของภาษาปกติและภาษาเชิงเหตุผล^{[ 9 ]}ผู้เขียนคนอื่นๆ เพียงแค่กำหนด "นิพจน์เชิงเหตุผล" และ "นิพจน์ปกติ" ว่ามีความหมายเหมือนกัน และทำเช่นเดียวกันกับ "ภาษาเชิงเหตุผล" และ "ภาษาปกติ" ^{[ 1 ] [ 2 ]}

เห็นได้ชัดว่าคำว่า"ปกติ"มีที่มาจากรายงานทางเทคนิคในปี 1951 ซึ่ง Kleene ได้แนะนำเหตุการณ์ปกติและยินดีรับ "ข้อเสนอแนะใดๆ เกี่ยวกับคำที่อธิบายได้ดียิ่งขึ้น" ^{[ 10 ]} Noam Chomskyในบทความสำคัญของเขาในปี 1959 ได้ใช้คำว่า"ปกติ"ในความหมายที่แตกต่างออกไปในตอนแรก (โดยอ้างถึงสิ่งที่เรียกว่ารูปแบบปกติของ Chomskyในปัจจุบัน) ^{[ 11 ]}แต่สังเกตเห็นว่าภาษาสถานะจำกัด ของเขา เทียบเท่ากับเหตุการณ์ปกติ ของ Kleene ^{[ 12 ]}

ภาษาปกติ (Regular languages) มีคุณสมบัติปิดภายใต้การดำเนินการต่างๆ กล่าวคือ ถ้าภาษาKและLเป็นภาษาปกติ ผลลัพธ์ของการดำเนินการต่อไปนี้ก็จะเป็นภาษาปกติเช่นกัน:

• การ ดำเนินการบูลีนเชิงทฤษฎีเซต : ยูเนียนK ∪ L อินเตอร์เซกชันK ∩ Lและคอมพลีเมนต์Lดังนั้นจึงรวมถึงคอมพลีเมนต์สัมพัทธ์K − Lด้วย^{[ 13 ]}
• การดำเนินการปกติ^: K ∪ L การเชื่อมต่อ${\displaystyle K\circ L}$และKleene ^star L ^* [ ¹⁴ ]
• การดำเนินการ สามอย่าง : โฮโมมอร์ฟิซึมของสตริงโฮโมมอร์ฟิซึมของสตริงผกผัน และการตัดกันกับภาษาปกติ ผลที่ตามมาคือภาษาเหล่านี้ปิดภายใต้การแปลงสถานะจำกัด ใดๆ เช่นผลหารK / L กับภาษาปกติ ยิ่งไปกว่านั้น ภาษาปกติยังปิดภายใต้ผลหารกับ ภาษา ใดๆ : ถ้าLเป็นภาษาปกติแล้วL / K ก็เป็น ภาษาปกติสำหรับK ใดๆ ^{[ 15 ]}
• L ^Rย้อนกลับ (หรือภาพสะท้อน) [ ^{16 ] เมื่อ}กำหนดออโตมาตอนจำกัดแบบไม่กำหนดเพื่อรับรู้LออโตมาตอนสำหรับL ^Rสามารถสร้างได้โดยการย้อนกลับการเปลี่ยนสถานะทั้งหมดและสลับสถานะเริ่มต้นและสถานะสิ้นสุด ซึ่งอาจส่งผลให้มีสถานะเริ่มต้นหลายสถานะ สามารถใช้การเปลี่ยนสถานะ ε เพื่อเชื่อมต่อสถานะเหล่านั้นได้

เมื่อกำหนดออโตมาตาจำกัดเชิงกำหนดAและB สองตัวแล้ว จะสามารถตัดสินได้ว่าพวกมันยอมรับภาษาเดียวกันหรือไม่^{[ 17 ]} ด้วยเหตุนี้ การใช้ คุณสมบัติการปิด ข้างต้นปัญหาต่อไปนี้จึงสามารถตัดสินได้สำหรับออโตมาตาจำกัดเชิงกำหนดAและB ที่กำหนดให้โดยพลการ โดยมีภาษาที่ยอมรับคือ L และL ตามลำดับ:

• การบรรจุ: L ⊆ L   หรือ ไม่? ^{[หมายเหตุ 10 ]}
• การแยกตัวออกจากกัน: L ∩ L = {}  หรือ ไม่?
• ความว่างเปล่า: L = {}  หรือ ไม่?
• ความเป็นสากล: L = Σ ^*  ?
• การเป็นสมาชิก: เมื่อกำหนดให้a ∈ Σ ^{* แล้ว} a ∈ L หรือ ไม่?

สำหรับนิพจน์ปกติ ปัญหาความเป็นสากลเป็นปัญหาNP-completeอยู่แล้วสำหรับตัวอักษรเดี่ยว^{[ 18 ]} สำหรับตัวอักษรที่ใหญ่กว่า ปัญหานั้นเป็นPSPACE-complete [ ^{19 ] หาก}นิพจน์ปกติถูกขยายเพื่อให้สามารถใช้ตัวดำเนินการยกกำลังสอง ได้ด้วย โดยที่ " A ² " หมายถึงสิ่งเดียวกันกับ " AA " ก็ยังคงสามารถอธิบายได้เฉพาะภาษาปกติเท่านั้น แต่ปัญหาความเป็นสากลมีขอบเขตล่างของพื้นที่เลขชี้กำลัง^{[ 20 ] [ 21 ] [ 22 ]}และในความเป็นจริงแล้วเป็นปัญหาสมบูรณ์สำหรับพื้นที่เลขชี้กำลังเมื่อเทียบกับการลดเวลาพหุนาม^{[ 23 ]}

สำหรับตัวอักษรจำกัดที่กำหนดไว้ ทฤษฎีของเซตของภาษาทั้งหมด – พร้อมด้วยสตริง การเป็นสมาชิกของสตริงในภาษา และสำหรับแต่ละอักขระ ฟังก์ชันในการเพิ่มอักขระลงในสตริง (และไม่มีการดำเนินการอื่นใด) – สามารถตัดสินได้ และโครงสร้างย่อยพื้นฐาน^ขั้น ต่ำ ประกอบด้วยภาษาปกติอย่างแม่นยำ สำหรับตัวอักษรไบนารี ทฤษฎีนี้เรียกว่าS2S [ ^{24 ]}

ในทฤษฎีความซับซ้อนของการคำนวณคลาสความซับซ้อนของภาษาปกติทั้งหมดบางครั้งเรียกว่าREGULARหรือREGและเท่ากับDSPACE (O(1)) ซึ่งเป็นปัญหาการตัดสินใจที่สามารถแก้ไขได้ในพื้นที่คงที่ (พื้นที่ที่ใช้ไม่ขึ้นอยู่กับขนาดของอินพุต) REGULAR ≠ AC ⁰เนื่องจาก (โดยปริยาย) ประกอบด้วยปัญหาความเท่าเทียมกันของการพิจารณาว่าจำนวนบิต 1 ในอินพุตเป็นเลขคู่หรือเลขคี่ และปัญหานี้ไม่ได้อยู่ในAC ^{0 [ 25} ] ในทางกลับกันREGULARไม่ได้ประกอบด้วยAC ⁰เนื่องจากภาษาที่ไม่ใช่ภาษาปกติของพาลินโดรม^หรือภาษาที่ไม่ใช่ภาษาปกติ^{สามารถ}รับรู้ได้ในAC ⁰ ทั้งคู่ [ ^{26 ]}${\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}}$

หากภาษาไม่ปกติ จะต้องใช้เครื่องที่มีพื้นที่อย่างน้อยΩ (log log n )ในการรับรู้ (โดยที่nคือขนาดอินพุต) ^{[ 27 ]}กล่าวอีกนัยหนึ่งDSPACE( o (log log n ))เท่ากับคลาสของภาษาปกติ^{[ 27 ]}ในทางปฏิบัติ ปัญหาที่ไม่ปกติส่วนใหญ่จะถูกศึกษาในสภาพแวดล้อมที่มีพื้นที่อย่างน้อยลอการิทึมเนื่องจากนี่คือปริมาณพื้นที่ที่จำเป็นในการจัดเก็บตัวชี้ลงในเทปอินพุต^{[ 28 ]}

ในการระบุตำแหน่งของภาษาปกติในลำดับชั้นของ Chomskyพบว่าภาษาปกติทุกภาษาเป็นภาษาไร้บริบทแต่ในทางกลับกันนั้นไม่เป็นจริง ตัวอย่างเช่น ภาษาที่ประกอบด้วยสตริงทั้งหมดที่มีจำนวนaเท่ากับ จำนวน bนั้นเป็นภาษาไร้บริบทแต่ไม่ใช่ภาษาปกติ ในการพิสูจน์ว่าภาษาใดไม่ใช่ภาษาปกติ มักจะใช้ทฤษฎีบท Myhill–Nerodeและบทตั้ง pumping lemmaแนวทางอื่นๆ ได้แก่ การใช้คุณสมบัติการปิดของภาษาปกติ^{[ 29 ]}หรือการหา ปริมาณความซับซ้อน ของKolmogorov ^{[ 30 ]}

กลุ่มย่อยที่สำคัญของภาษาปกติ ได้แก่:

• ภาษาจำกัด คือภาษาที่มีคำเพียงจำนวนจำกัด^{[ 31 ]}ภาษาเหล่านี้เป็นภาษาปกติ เนื่องจากสามารถสร้างนิพจน์ปกติที่เป็นการรวมกันของทุกคำในภาษาได้
• ภาษาที่ปราศจากดาวคือภาษาที่สามารถอธิบายได้ด้วยนิพจน์ปกติที่สร้างขึ้นจากสัญลักษณ์ว่าง ตัวอักษร การต่อกัน และตัวดำเนินการบูลีนทั้งหมด (ดูพีชคณิตของเซต ) รวมถึงการเติมเต็มแต่ไม่รวมดาวคลีน : คลาสนี้รวมถึงภาษาจำกัดทั้งหมด^{[ 32 ]}

ให้ L แทนจำนวนคำที่มีความยาว L ในL ฟังก์ชันก่อกำเนิดปกติสำหรับLคืออนุกรมกำลังอย่างเป็นทางการ${\displaystyle s_{L}(n)}$${\displaystyle n}$${\displaystyle L}$

${\displaystyle S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .}$

ฟังก์ชันก่อกำเนิดของภาษาLเป็นฟังก์ชันตรรกยะถ้าLเป็นภาษาปกติ^{[ 33 ]} ดังนั้นสำหรับทุกภาษาปกติลำดับจะเป็นแบบเรียกซ้ำคงที่กล่าวคือ มีค่าคงที่จำนวนเต็มค่าคงที่เชิงซ้อนและพหุนาม เชิงซ้อนอยู่ ซึ่งสำหรับทุกจำนวนคำที่มีความ^ยาวในคือ^{[ 34} ] ^{[ 35 ] [ 36 ] [ 37 ]}${\displaystyle L}$${\displaystyle s_{L}(n)_{n\geq 0}}$${\displaystyle n_{0}}$${\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}}$${\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)}$${\displaystyle n\geq n_{0}}$${\displaystyle s_{L}(n)}$${\displaystyle n}$${\displaystyle L}$${\displaystyle s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}}$

ดังนั้น ความไม่สม่ำเสมอของภาษาบางภาษาสามารถพิสูจน์ได้โดยการนับคำที่มีความยาวที่กำหนดใน พิจารณาตัวอย่างเช่นภาษา Dyckของสตริงวงเล็บที่สมดุล จำนวนคำที่มีความยาว ในภาษา Dyck เท่ากับจำนวน Catalanซึ่งไม่ได้อยู่ในรูปแบบ ซึ่งแสดงให้เห็นถึงความไม่สม่ำเสมอของภาษา Dyck ต้องระมัดระวังเนื่องจากค่าลักษณะเฉพาะบางค่าอาจมีขนาดเท่ากัน ตัวอย่างเช่น จำนวนคำที่มีความยาวในภาษาของคำไบนารีคู่ทั้งหมดไม่ได้อยู่ในรูปแบบแต่จำนวนคำที่มีความยาวคู่หรือคี่อยู่ในรูปแบบนี้ ค่าลักษณะเฉพาะที่สอดคล้องกันคือโดยทั่วไป สำหรับทุกภาษาปกติจะมีค่าคงที่เช่นนั้นสำหรับทุกจำนวนคำที่มีความยาวจะมีค่าประมาณ^{[ 38 ]}${\displaystyle L'}$${\displaystyle L'}$${\displaystyle 2n}$${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}}$${\displaystyle p(n)\lambda ^{n}}$${\displaystyle \lambda _{i}}$${\displaystyle n}$${\displaystyle p(n)\lambda ^{n}}$${\displaystyle 2,-2}$${\displaystyle d}$${\displaystyle a}$${\displaystyle dm+a}$${\displaystyle C_{a}m^{p_{a}}\lambda _{a}^{m}}$

ฟังก์ชันซีตาของภาษาLคือ^{[ 33 ]}

${\displaystyle \zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right)}$

ฟังก์ชันซีตาของภาษาปกติโดยทั่วไปไม่ใช่ฟังก์ชันเชิงตรรกะ แต่ฟังก์ชันซีตาของภาษาวัฏจักร ใดๆ ก็ตามเป็นฟังก์ชัน เชิงตรรกะ ^{[ 39 ] [ 40 ]}

แนวคิดเรื่องภาษาปกติได้รับการขยายไปสู่คำอนันต์ (ดูω-automata ) และต้นไม้ (ดูtree automaton )

เซตตรรกะเป็นการสรุปแนวคิด (ของภาษาปกติ/ตรรกะ) ไปยังโมโนอิดที่ไม่จำเป็นต้องเป็นอิสระในทำนองเดียวกัน แนวคิดของภาษาที่รับรู้ได้ (โดยออโตมาตาจำกัด) มีชื่อมาจากเซตที่รับรู้ได้เหนือโมโนอิดที่ไม่จำเป็นต้องเป็นอิสระ Howard Straubing ตั้งข้อสังเกตเกี่ยวกับข้อเท็จจริงเหล่านี้ว่า “คำว่า “ภาษาปกติ” ค่อนข้างไม่เหมาะสม บทความที่ได้รับอิทธิพลจากงานวิจัยของEilenberg ^{[ 41 ]}มักใช้คำว่า “ภาษาที่รับรู้ได้” ซึ่งหมายถึงพฤติกรรมของออโตมาตา หรือ “ภาษาตรรกะ” ซึ่งหมายถึงความคล้ายคลึงที่สำคัญระหว่างนิพจน์ปกติและอนุกรมกำลัง ตรรกะ (อันที่จริง Eilenberg กำหนดเซตย่อยตรรกะและที่รับรู้ได้ของโมโนอิดตามอำเภอใจ แนวคิดทั้งสองโดยทั่วไปไม่ตรงกัน) คำศัพท์นี้ถึงแม้จะมีแรงจูงใจที่ดีกว่า แต่ก็ไม่ได้รับความนิยม และ “ภาษาปกติ” ถูกใช้กันอย่างแพร่หลาย” ^{[ 42 ]}

อนุกรมตรรกยะเป็นการวางนัยทั่วไปอีกแบบหนึ่ง คราวนี้ในบริบทของอนุกรมกำลังอย่างเป็นทางการเหนือเซมิริงแนวทางนี้ก่อให้เกิดนิพจน์ตรรกยะแบบถ่วงน้ำหนักและออโตมาตาแบบถ่วงน้ำหนักในบริบทพีชคณิตนี้ ภาษาปกติ (ที่สอดคล้องกับ นิพจน์ตรรกยะแบบถ่วงน้ำหนัก บูลีน ) มักเรียกว่าภาษาตรรกยะ [ ^{43 ] [ 44 ] ใน}บริบทนี้เช่นกัน ทฤษฎีบทของ Kleene พบการวางนัยทั่วไปที่เรียกว่า ทฤษฎีบท Kleene –Schützenberger

• Kleene, SC : การแสดงเหตุการณ์ในโครงข่ายประสาทและออโตมาตาจำกัด ใน: Shannon, CE, McCarthy, J. (บรรณาธิการ) Automata Studies, หน้า 3–41. สำนักพิมพ์มหาวิทยาลัยพรินซ์ตัน, พรินซ์ตัน (1956) ;  เป็นฉบับที่ปรับปรุงเล็กน้อยจากรายงานของRAND Corporation ปี 1951 ที่มีชื่อเดียวกันRM704
• Sakarovitch, J ( 1987). "ทฤษฎีบทของ Kleene ฉบับปรับปรุงใหม่" แนวโน้ม เทคนิค และปัญหาในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์ เล่มที่ 1987 หน้า39–50 doi : 10.1007/3540185356_29 ISBN  978-3-540-18535-2.

• Complexity Zoo : คลาส REG