ไวยากรณ์ที่คลุมเครือ

Q: สตริงเอกภาค

ภาษา ปกติ ของสตริงเอกภาคที่มีอักขระที่กำหนด เช่น 'a' (นิพจน์ปกติ a* ) มีไวยากรณ์ที่ชัดเจนดังนี้:

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

สำหรับภาษาการเขียนโปรแกรม คอมพิวเตอร์ ไวยากรณ์อ้างอิงมักจะกำกวมเนื่องจากปัญหาต่างๆ เช่น ปัญหา else ที่ไม่มีอยู่จริงหากพบความกำกวมเหล่านี้ โดยทั่วไปจะแก้ไขได้โดยการเพิ่มกฎลำดับความสำคัญหรือ กฎการแยกวิเคราะห์ ตามบริบท อื่นๆ เพื่อให้ไวยากรณ์วลีโดยรวมไม่กำกวมอัลกอริทึมการแยกวิเคราะห์บางอย่าง (เช่นEarley ^[³^]หรือ ตัวแยกวิเคราะห์ GLR ) สามารถสร้างชุดของต้นไม้การแยกวิเคราะห์ (หรือ "ป่าการแยกวิเคราะห์") จากสตริงที่มีความกำกวมทางไวยากรณ์^[⁴^]

ตัวอย่าง

ภาษาที่ไร้สาระ

ตัวอย่างที่ง่ายที่สุดคือไวยากรณ์กำกวมต่อไปนี้ (โดยมีสัญลักษณ์เริ่มต้นเป็น A) สำหรับภาษาที่ไม่สำคัญซึ่งประกอบด้วยสตริงว่างเพียงอย่างเดียว:

A → A | ε

...หมายความว่า สัญลักษณ์ที่ไม่ใช่เทอร์มินัล A สามารถอนุมานได้กลับไปเป็นตัวมันเองอีกครั้ง หรือไปเป็นสตริงว่าง ดังนั้น สตริงว่างจึงมีการอนุมานจากซ้ายสุดที่มีความยาว 1, 2, 3 และความยาวใดๆ ก็ได้ ขึ้นอยู่กับว่าใช้กฎ A → A กี่ครั้ง

ภาษานี้ยังมีไวยากรณ์ที่ชัดเจน โดยประกอบด้วยกฎการสร้าง เพียงข้อเดียว :

A → ε

...หมายความว่ากฎการสร้างเอกลักษณ์สามารถสร้างได้เพียงสตริงว่าง ซึ่งเป็นสตริงเดียวในภาษา

ในทำนองเดียวกัน ไวยากรณ์ใดๆ สำหรับภาษาที่ไม่ว่างเปล่า สามารถทำให้กำกวมได้โดยการเพิ่มคำซ้ำเข้าไป

สตริงเอกภาค

ภาษาปกติของสตริงเอกภาคที่มีอักขระที่กำหนด เช่น'a'(นิพจน์ปกติa*) มีไวยากรณ์ที่ชัดเจนดังนี้:

A → aA | ε

...แต่ก็มีไวยากรณ์ที่คลุมเครือด้วยเช่นกัน:

A → aA | Aa | ε

สิ่งเหล่านี้สอดคล้องกับการสร้าง แผนผัง การเชื่อมโยงทางขวา (สำหรับไวยากรณ์ที่ไม่กำกวม) หรือการอนุญาตให้มีการเชื่อมโยงทั้งทางซ้ายและขวา ซึ่งจะอธิบายรายละเอียดเพิ่มเติมด้านล่าง

การบวกและการลบ

ไวยากรณ์ที่ไม่ขึ้นกับบริบท

A → A + A | A − A | a

มีความกำกวมเนื่องจากมีอนุพันธ์ซ้ายสุดสองแบบสำหรับสตริง a + a + a:

เอ	→ เอ + เอ	เอ	→ เอ + เอ
	→ a + A		→ A + A + A (แทนที่ A ตัวแรกด้วย A+A การแทนที่ A ตัวที่สองจะให้ผลลัพธ์ที่คล้ายกัน)
	→ a + A + A		→ a + A + A
	→ a + a + A		→ a + a + A
	→ a + a + a		→ a + a + a

ตัวอย่างเช่น ไวยากรณ์มีความกำกวมเนื่องจากมีแผนผังการวิเคราะห์ สองแบบ สำหรับสตริง a + a − a:

อย่างไรก็ตาม ภาษาที่สร้างขึ้นนั้นไม่ได้มีความกำกวมโดยเนื้อแท้ ไวยากรณ์ต่อไปนี้เป็นไวยากรณ์ที่ไม่กำกวมซึ่งสร้างภาษาเดียวกัน:

A → A + a | A − a | a

ห้อยลงมาอย่างอื่น

ตัวอย่างทั่วไปของความกำกวมในภาษาโปรแกรมคอมพิวเตอร์คือ ปัญหา else ที่ไม่มีอยู่จริงในหลายภาษา เงื่อนไข else elseใน คำสั่ง If–then(–else)นั้นเป็นตัวเลือก ซึ่งส่งผลให้เงื่อนไขที่ซ้อนกันมีหลายวิธีในการตีความตามไวยากรณ์แบบไร้บริบท

กล่าวโดยเฉพาะเจาะจง ในหลายภาษา เราสามารถเขียนประโยคเงื่อนไขได้สองรูปแบบที่ถูกต้อง คือ รูปแบบ if-then และรูปแบบ if-then-else ซึ่งในทางปฏิบัติแล้ว ส่วน else นั้นเป็นส่วนเสริมที่ไม่จำเป็น

ในไวยากรณ์ที่มีกฎ^[ก]

คำสั่ง → ถ้าเงื่อนไขเป็นจริงคำสั่ง | ถ้าเงื่อนไขเป็น จริง คำสั่งมิฉะนั้นคำสั่ง | ... เงื่อนไข → ...

อาจมีโครงสร้างวลีที่ไม่ชัดเจนปรากฏขึ้นได้ เช่น สำนวน

ถ้า a แล้วถ้า b แล้ว s มิฉะนั้น s2

สามารถแยกวิเคราะห์ได้เป็นอย่างใดอย่างหนึ่ง

ถ้า a แล้วเริ่มถ้า b แล้ว s จบมิฉะนั้น s2

หรือเช่น

ถ้า a แล้วเริ่มถ้า b แล้ว s มิฉะนั้น s2 สิ้นสุด

ขึ้นอยู่กับว่าelseเกี่ยวข้องกับอันแรกifหรืออันที่ifสอง

ปัญหานี้ได้รับการแก้ไขในหลายวิธีในภาษาต่างๆ บางครั้งไวยากรณ์จะถูกปรับเปลี่ยนเพื่อให้ไม่มีความกำกวม เช่น โดยการกำหนดให้มีendifประโยคบอกเล่าหรือทำให้เป็นelseข้อบังคับ ในบางกรณี ไวยากรณ์ยังคงมีความกำกวม แต่ความกำกวมนั้นจะได้รับการแก้ไขโดยการทำให้ไวยากรณ์ของวลีโดยรวมขึ้นอยู่กับบริบท เช่น โดยการเชื่อมโยงคำว่า "an" elseกับคำที่อยู่ใกล้ที่สุดifในกรณีหลังนี้ ไวยากรณ์จะไม่มีความกำกวม แต่ไวยากรณ์ที่ไม่ขึ้นกับบริบทจะมีความกำกวม

ไวยากรณ์ที่ชัดเจนพร้อมการสร้างคำหลายรูปแบบ

การมีโครงสร้างประโยคเดียวกันหลายแบบไม่ได้หมายความว่าไวยากรณ์นั้นกำกวม มีเพียง โครงสร้างประโยค ซ้ายสุด หลายแบบ (หรือเทียบเท่ากับโครงสร้างต้นไม้การวิเคราะห์ไวยากรณ์หลายแบบ) เท่านั้นที่บ่งชี้ถึงความกำกวม

ตัวอย่างเช่น ไวยากรณ์แบบง่าย

S → A + A A → 0 | 1

เป็นไวยากรณ์ที่ไม่กำกวมสำหรับภาษา { 0+0, 0+1, 1+0, 1+1 } ในขณะที่สตริงทั้งสี่นี้มีเพียงการสร้างแบบซ้ายสุดเพียงหนึ่งเดียว แต่ก็มีการสร้างที่แตกต่างกันสองแบบ ตัวอย่างเช่น

S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0

และ

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

มีเพียงการอนุมานแบบแรกเท่านั้นที่เป็นการอนุมานจากซ้ายสุด

การระบุไวยากรณ์ที่คลุมเครือ

ปัญหาการตัดสินใจว่าไวยากรณ์ใดๆ กำกวมหรือไม่นั้นไม่สามารถตัดสินได้เนื่องจากสามารถแสดงได้ว่าเทียบเท่ากับปัญหาการประสานงานของโพสต์ [ ^{5 ] อย่าง}น้อยที่สุดก็มีเครื่องมือที่ใช้ขั้นตอนกึ่งตัดสินใจ บางอย่าง เพื่อตรวจจับความกำกวมของไวยากรณ์แบบไร้บริบท^{[ 6 ]}

ประสิทธิภาพของการแยกวิเคราะห์ไวยากรณ์แบบไร้บริบทจะถูกกำหนดโดยออโตมาตอนที่ยอมรับไวยากรณ์นั้นไวยากรณ์แบบไร้ บริบทเชิงกำหนด จะได้รับการยอมรับโดยออโตมาตอนแบบพุชดาวน์เชิงกำหนดและสามารถแยกวิเคราะห์ได้ในเวลาเชิงเส้น เช่น โดย ตัวแยก วิเคราะห์LR ^{[ 7 ]}ไวยากรณ์เหล่านี้เป็นเซตย่อยที่เข้มงวดของไวยากรณ์แบบไร้บริบทซึ่งได้รับการยอมรับโดยออโตมาตอนแบบพุชดาวน์และสามารถแยกวิเคราะห์ได้ในเวลาพหุนาม เช่น โดยอัลกอริทึม CYK

ไวยากรณ์แบบไร้บริบทที่ไม่กำกวมสามารถเป็นแบบไม่แน่นอนได้ ตัวอย่างเช่น ภาษาของพาลินโดรมที่ มีความยาวคู่ บนตัวอักษร 0 และ 1 มีไวยากรณ์แบบไร้บริบทที่ไม่กำกวม S → 0S0 | 1S1 | ε สตริงใดๆ ของภาษานี้ไม่สามารถแยกวิเคราะห์ได้โดยไม่ต้องอ่านสัญลักษณ์ทั้งหมดก่อน ซึ่งหมายความว่าออโตมาตาแบบพุชดาวน์ต้องลองการเปลี่ยนสถานะทางเลือกเพื่อรองรับความยาวที่เป็นไปได้ต่างๆ ของสตริงที่แยกวิเคราะห์บางส่วน^{[ 8 ]}

อย่างไรก็ตาม การขจัดความกำกวมทางไวยากรณ์อาจทำให้เกิดไวยากรณ์แบบบริบทอิสระที่กำหนดได้ และทำให้การวิเคราะห์ไวยากรณ์มีประสิทธิภาพมากขึ้น ตัวสร้างคอมไพเลอร์ เช่นYACCมีคุณสมบัติในการแก้ไขความกำกวมบางประเภท เช่น การใช้ข้อจำกัดด้านลำดับความสำคัญและการเชื่อมโยง

ภาษาที่มีความกำกวมโดยเนื้อแท้

ในขณะที่ภาษาไร้บริบทบางภาษา (เซตของสตริงที่สามารถสร้างขึ้นได้จากไวยากรณ์) มีทั้งไวยากรณ์ที่กำกวมและไม่กำกวม แต่ก็มีภาษาไร้บริบทบางภาษาที่ไม่มีไวยากรณ์ไร้บริบทที่ไม่กำกวมอยู่เลย ภาษาเหล่านั้นเรียกว่า ภาษาที่กำกวมโดยเนื้อแท้

ไม่มีภาษาปกติใดที่กำกวมโดยเนื้อแท้^{[ 9 ]}^{[ 10 ]}

การมีอยู่ของภาษาที่ไม่ขึ้นกับบริบทซึ่งมีความกำกวมโดยเนื้อแท้ได้รับการพิสูจน์ด้วยทฤษฎีบทของ Parikhในปี พ.ศ. 2504 โดยRohit Parikhในรายงานการวิจัยของ MIT ^{[ 11 ]}

ภาษา $\{x|x=a^{n}b^{m}a^{n^{\prime }}b^{m}{\text{ หรือ }}x=a^{n}b^{m}a^{n}b^{m^{\prime }},{\text{ โดยที่ }}n,n',m,m'\geq 1\}$ มีความคลุมเครือโดยเนื้อแท้^{[ 12 ]}

บทพิสูจน์ของ Ogden ^{[ 13 ]}สามารถใช้เพื่อพิสูจน์ว่าภาษาที่ไม่ขึ้นกับบริบทบางภาษา เช่น $\{a^{n}b^{m}c^{m}|m,n\geq 1\}\cup \{a^{m}b^{m}c^{n}|m,n\geq 1\}$ ซึ่งโดยเนื้อแท้แล้วมีความกำกวม ดูบทพิสูจน์ได้จากทฤษฎีบทของ Ogden ในหัวข้อ § ความกำกวมโดยเนื้อแท้

สหภาพของ $\{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}$ กับ $\{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}$ มีความกำกวมโดยเนื้อแท้ เซตนี้เป็นภาษาไร้บริบท เนื่องจากผลรวมของภาษาไร้บริบทสองภาษาจะเป็นภาษาไร้บริบทเสมอ แต่Hopcroft & Ullman (1979)ได้พิสูจน์ว่าไม่มีไวยากรณ์ไร้บริบทใดสำหรับภาษารวมนี้ที่สามารถวิเคราะห์สตริงในรูปแบบได้อย่างชัดเจน $a^{n}b^{n}c^{n}d^{n},(n>0)$ [ ¹⁴^]

ตัวอย่างเพิ่มเติมและการทบทวนทั่วไปของเทคนิคในการพิสูจน์ความกำกวมโดยธรรมชาติของภาษาที่ไม่ขึ้นกับบริบท สามารถพบได้ใน Bassino และ Nicaud (2011) ^{[ 15 ]}

ดูเพิ่มเติม

GLR parserคือตัวแยกวิเคราะห์ประเภทหนึ่งสำหรับไวยากรณ์ที่ไม่ชัดเจนและไม่แน่นอน
ตัวแยกวิเคราะห์แผนภูมิ (Chart parser ) ซึ่งเป็น ตัวแยกวิเคราะห์อีกประเภทหนึ่งสำหรับไวยากรณ์ที่ไม่ชัดเจน
ความกำกวมทางไวยากรณ์

การอ้างอิง

หมายเหตุ

↑ตัวอย่างต่อไปนี้ใช้ไวยากรณ์ภาษาปาสคาล

เอกสารอ้างอิง

↑ Willem JM Levelt (2008). An Introduction to the Theory of Formal Languages and Automata . John Benjamins Publishing. ISBN 978-90-272-3250-2.
↑ Hopcroft, Motwani & Ullman 2006 , หน้า 217.
↑ Scott, Elizabeth (1 เมษายน 2551). "การแยกวิเคราะห์แบบ SPPF จากตัวรู้จำแบบ Earlyly" . Electronic Notes in Theoretical Computer Science . 203 (2): 53– 67. doi : 10.1016/j.entcs.2008.03.044 .
↑ Tomita, Masaru. "อัลกอริทึมการแยกวิเคราะห์แบบอิสระบริบทเสริมที่มีประสิทธิภาพ " ภาษาศาสตร์เชิงคำนวณ 13.1-2 (1987): 31-46.
↑ฮอปครอฟต์, มอทวานีและอุลมาน 2549 , หน้า. 415 ทฤษฎีบท 9.20
↑ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "การวิเคราะห์ไวยากรณ์แบบไร้บริบทโดยใช้ตัวแก้ปัญหา SAT แบบเพิ่มทีละขั้น" (PDF) . รายงานการประชุมวิชาการนานาชาติครั้งที่ 35 ว่าด้วยออโตมาตา ภาษา และการเขียนโปรแกรม (ICALP'08) เรคยาวิก ประเทศไอซ์แลนด์ . Lecture Notes in Computer Science . เล่มที่5126. Springer-Verlag. หน้า410– 422. doi : 10.1007/978-3-540-70583-3_34 . ISBN 978-3-540-70582-6.
↑ Knuth, DE (กรกฎาคม 1965). "เกี่ยวกับการแปลภาษาจากซ้ายไปขวา". ข้อมูลและการควบคุม 8 ( 6): 607– 639. doi : 10.1016/S0019-9958(65)90426-2 .
↑ Hopcroft, Motwani & Ullman 2006 , หน้า 254–6.
↑ Book, R.; Even, S.; Greibach, S.; Ott, G. (กุมภาพันธ์ 1971). "ความกำกวมในกราฟและนิพจน์" . IEEE Transactions on Computers . C-20 (2): 149– 153. doi : 10.1109/tc.1971.223204 . ISSN 0018-9340 . S2CID 20676251 .
↑ "ภาษาเชิงรูปธรรม - นิพจน์ปกติสามารถทำให้ไม่กำกวมได้หรือไม่?" . MathOverflow . สืบค้นเมื่อ2023-02-23 .
↑ปาริค, โรหิต (มกราคม 1961). อุปกรณ์สร้างภาษา . รายงานความคืบหน้าประจำไตรมาส, ห้องปฏิบัติการวิจัยอิเล็กทรอนิกส์, MIT.
↑ Parikh, Rohit J. (1966-10-01). "เกี่ยวกับภาษาที่ไม่ขึ้นกับบริบท" . Journal of the ACM . 13 (4): 570– 581. doi : 10.1145/321356.321364 . ISSN 0004-5411 . S2CID 12263468 . นี่คือทฤษฎีบทที่ 3
↑ Ogden, William (ก.ย. 1968). "ผลลัพธ์ที่เป็นประโยชน์สำหรับการพิสูจน์ความกำกวมโดยธรรมชาติ"ทฤษฎีระบบคณิตศาสตร์2 (3): 191– 194. doi : 10.1007/bf01694004 . ISSN 0025-5661 . S2CID 13197551 .
↑ Hopcroft & Ullman 1979 , หน้า 99-103, ส่วนที่ 4.7.
↑ Fredérique Bassino และ Cyril Nicaud (16 ธันวาคม 2011). "Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages" (PDF) . เก็บถาวร(PDF)จากต้นฉบับเมื่อ 25 กันยายน 2022

ฮอปครอฟต์, จอห์น อี.; อัลแมน, เจฟฟรีย์ ดี. (1979). บทนำสู่ทฤษฎีออโตมาตา ภาษา และการคำนวณ ( ฉบับพิมพ์ครั้งที่ 1). แอดดิสัน-เวสลีย์. ISBN 0-201-02988-X.( สามารถเข้าถึงได้สำหรับผู้ใช้บริการที่มีความบกพร่องทางการอ่าน )
Hopcroft, John E. ; Motwani, Rajeev ; Ullman, Jeffrey D. (2006) [1979]. บทนำสู่ทฤษฎีออโตมาตา ภาษา และการคำนวณ ( ฉบับที่ 3). Addison-Wesley. ISBN 0-321-45536-3.

อ่านเพิ่มเติม

Brabrand, Claus; Giegerich, Robert; Møller, Anders (มีนาคม 2010). "การวิเคราะห์ความกำกวมของไวยากรณ์แบบไร้บริบท". วิทยาศาสตร์ของการ เขียนโปรแกรมคอมพิวเตอร์75 (3). Elsevier: 176– 191. CiteSeerX 10.1.1.86.3118 . doi : 10.1016/j.scico.2009.11.002 .
Gross, Maurice (กันยายน 1964). "ความกำกวมโดยธรรมชาติของไวยากรณ์เชิงเส้นขั้นต่ำ" . ข้อมูลและการควบคุม . 7 (3): 366– 368. doi : 10.1016/S0019-9958(64)90422-X .
แฮร์ริสัน, ไมเคิล (1978). บทนำสู่ทฤษฎีภาษาเชิงรูปธรรม . แอดดิสัน-เวสลีย์. ISBN 0201029553.

ลิงก์ภายนอก

dk.brics.grammar - เครื่องมือวิเคราะห์ความกำกวมทางไวยากรณ์
CFGAnalyzer - เครื่องมือสำหรับวิเคราะห์ไวยากรณ์แบบไม่ขึ้นกับบริบท โดยคำนึงถึงความเป็นสากลของภาษา ความกำกวม และคุณสมบัติที่คล้ายคลึงกัน

[5] ตัวอย่างต่อไปนี้ใช้ไวยากรณ์ภาษาปาสคาล

[Levelt2008-1] Willem JM Levelt (2008). An Introduction to the Theory of Formal Languages and Automata . John Benjamins Publishing. ISBN 978-90-272-3250-2.

[FOOTNOTEHopcroftMotwaniUllman2006217-2] Hopcroft, Motwani & Ullman 2006 , หน้า 217.

[3] Scott, Elizabeth (1 เมษายน 2551). "การแยกวิเคราะห์แบบ SPPF จากตัวรู้จำแบบ Earlyly" . Electronic Notes in Theoretical Computer Science . 203 (2): 53– 67. doi : 10.1016/j.entcs.2008.03.044 .

[4] Tomita, Masaru. "อัลกอริทึมการแยกวิเคราะห์แบบอิสระบริบทเสริมที่มีประสิทธิภาพ " ภาษาศาสตร์เชิงคำนวณ 13.1-2 (1987): 31-46.

[FOOTNOTEHopcroftMotwaniUllman2006415Theorem_9.20-6] ฮอปครอฟต์, มอทวานีและอุลมาน 2549 , หน้า. 415 ทฤษฎีบท 9.20

[7] Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "การวิเคราะห์ไวยากรณ์แบบไร้บริบทโดยใช้ตัวแก้ปัญหา SAT แบบเพิ่มทีละขั้น" (PDF) . รายงานการประชุมวิชาการนานาชาติครั้งที่ 35 ว่าด้วยออโตมาตา ภาษา และการเขียนโปรแกรม (ICALP'08) เรคยาวิก ประเทศไอซ์แลนด์ . Lecture Notes in Computer Science . เล่มที่5126. Springer-Verlag. หน้า410– 422. doi : 10.1007/978-3-540-70583-3_34 . ISBN 978-3-540-70582-6.

[8] Knuth, DE (กรกฎาคม 1965). "เกี่ยวกับการแปลภาษาจากซ้ายไปขวา". ข้อมูลและการควบคุม 8 ( 6): 607– 639. doi : 10.1016/S0019-9958(65)90426-2 .

[FOOTNOTEHopcroftMotwaniUllman2006254–6-9] Hopcroft, Motwani & Ullman 2006 , หน้า 254–6.

[10] Book, R.; Even, S.; Greibach, S.; Ott, G. (กุมภาพันธ์ 1971). "ความกำกวมในกราฟและนิพจน์" . IEEE Transactions on Computers . C-20 (2): 149– 153. doi : 10.1109/tc.1971.223204 . ISSN 0018-9340 . S2CID 20676251 .

[11] "ภาษาเชิงรูปธรรม - นิพจน์ปกติสามารถทำให้ไม่กำกวมได้หรือไม่?" . MathOverflow . สืบค้นเมื่อ2023-02-23 .

[12] ปาริค, โรหิต (มกราคม 1961). อุปกรณ์สร้างภาษา . รายงานความคืบหน้าประจำไตรมาส, ห้องปฏิบัติการวิจัยอิเล็กทรอนิกส์, MIT.

[13] Parikh, Rohit J. (1966-10-01). "เกี่ยวกับภาษาที่ไม่ขึ้นกับบริบท" . Journal of the ACM . 13 (4): 570– 581. doi : 10.1145/321356.321364 . ISSN 0004-5411 . S2CID 12263468 . นี่คือทฤษฎีบทที่ 3

[14] Ogden, William (ก.ย. 1968). "ผลลัพธ์ที่เป็นประโยชน์สำหรับการพิสูจน์ความกำกวมโดยธรรมชาติ"ทฤษฎีระบบคณิตศาสตร์2 (3): 191– 194. doi : 10.1007/bf01694004 . ISSN 0025-5661 . S2CID 13197551 .

[FOOTNOTEHopcroftUllman197999-103Sect._4.7-15] Hopcroft & Ullman 1979 , หน้า 99-103, ส่วนที่ 4.7.

[16] Fredérique Bassino และ Cyril Nicaud (16 ธันวาคม 2011). "Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages" (PDF) . เก็บถาวร(PDF)จากต้นฉบับเมื่อ 25 กันยายน 2022

[ 1 ]

[ 2 ]

[

[

[ก]

5 ] อย่าง

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

14

[ 15 ]