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

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

PDA (ซึ่งไม่จำเป็นต้องเป็นแบบกำหนดได้แน่นอน) สามารถนิยามได้ว่าเป็น 7-tuple ดังนี้: ${\displaystyle M}$

${\displaystyle M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,Z_{0}\,,A\,,\delta \,)}$

ที่ไหน

• ${\displaystyle Q\,}$เป็นเซตของสถานะที่มีจำนวนจำกัด
• ${\displaystyle \Sigma \,}$เป็นเซตจำกัดของสัญลักษณ์อินพุต
• ${\displaystyle \Gamma \,}$เป็นเซตจำกัดของสัญลักษณ์สแต็ก
• ${\displaystyle q_{0}\,\in Q\,}$คือสถานะเริ่มต้น
• ${\displaystyle Z_{0}\,\in \Gamma \,}$คือสัญลักษณ์สแต็กเริ่มต้น
• ${\displaystyle A\,\subseteq Q\,}$โดย ที่เซตของสถานะที่ยอมรับหรือสถานะสุดท้ายอยู่ที่ไหน${\displaystyle A}$
• ${\displaystyle \delta \,}$เป็นฟังก์ชันการเปลี่ยนผ่าน โดยที่

${\displaystyle \delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$

โดยที่Kleene starหมายถึง"เซตของสตริงจำกัดทั้งหมด (รวมถึงสตริงว่าง ) ของสมาชิกใน", แทนสตริงว่างและคือเซตกำลังของเซต${\displaystyle *}$${\displaystyle \Gamma ^{*}}$${\displaystyle \varepsilon }$${\displaystyle \Gamma }$${\displaystyle \varepsilon }$${\displaystyle {\mathcal {P}}(X)}$${\displaystyle X}$

Mเป็นแบบกำหนดได้แน่นอน (deterministic)ถ้าเป็นไปตามเงื่อนไขทั้งสองข้อต่อไปนี้:

• สำหรับค่าใดๆเซตนั้นจะมีสมาชิกอย่างมากที่สุดเพียงหนึ่งเดียว${\displaystyle q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma }$${\displaystyle \delta (q,a,x)\,}$
• สำหรับทุก ๆถ้าแล้วสำหรับทุก ๆ${\displaystyle q\in Q,x\in \Gamma }$${\displaystyle \delta (q,\varepsilon ,x)\not =\emptyset \,}$${\displaystyle \delta \left(q,a,x\right)=\emptyset }$${\displaystyle a\in \Sigma .}$

มีเกณฑ์การยอมรับที่เป็นไปได้สองประการ ได้แก่ การยอมรับโดยสแต็กว่างและการยอมรับโดยสถานะสุดท้ายทั้งสองไม่เท่ากันสำหรับออโตมาตาพุชดาวน์แบบกำหนด (แม้ว่าจะเท่ากันสำหรับออโตมาตาพุชดาวน์แบบไม่กำหนด) ภาษาที่ยอมรับโดยสแต็กว่างคือภาษาที่ยอมรับโดยสถานะสุดท้ายและไม่มีคำนำหน้า: ไม่มีคำใดในภาษาเป็นคำนำหน้าของคำอื่นในภาษา^{[ 2 ] [ 3 ]}

เกณฑ์การยอมรับโดยทั่วไปคือสถานะสุดท้ายและเกณฑ์การยอมรับนี้เองที่ใช้ในการกำหนดภาษาบริบทอิสระเชิงกำหนด

ถ้าภาษาหนึ่งได้รับการยอมรับจาก PDA แล้ว ภาษานั้นก็จะได้รับการยอมรับจาก DPDA ได้เช่นกัน ก็ต่อเมื่อมีการคำนวณเพียงครั้งเดียวตั้งแต่การกำหนดค่าเริ่มต้นจนถึงการกำหนดค่าที่ยอมรับได้สำหรับสตริงทั้งหมดที่อยู่ในนั้นถ้าภาษาหนึ่งได้รับการยอมรับจาก PDA แล้ว ภาษานั้นจะเป็นภาษาไร้บริบท และถ้าภาษานั้นได้รับการยอมรับจาก DPDA แล้ว ภาษานั้นจะเป็นภาษาไร้บริบทเชิงกำหนด (DCFL) ${\displaystyle L(A)}$${\displaystyle A}$${\displaystyle L(A)}$${\displaystyle L(A)}$

ไม่ใช่ทุกภาษาแบบไร้บริบทจะเป็นแบบกำหนดได้ นี่ทำให้ DPDA เป็นอุปกรณ์ที่อ่อนแอกว่า PDA อย่างเห็นได้ชัด ตัวอย่างเช่น ภาษาL _{p ซึ่งประกอบด้วย} พาลินโดรมความยาวคู่บนตัวอักษร 0 และ 1 มีไวยากรณ์แบบไร้บริบท S → 0S0 | 1S1 | ε ถ้ามี DPDA สำหรับภาษานี้อยู่ และมันเห็นสตริง 0 ⁿมันจะต้องใช้สแต็กเพื่อจดจำความยาวnเพื่อที่จะสามารถแยกแยะความต่อเนื่องที่เป็นไปได้0 ⁿ 11 0 ⁿ ∈ L _pและ0 ⁿ 11 0 ^{n +2} ∉ L _pได้ดังนั้น หลังจากอ่าน0 ⁿ 11 0 ⁿแล้วการเปรียบเทียบความยาวหลัง "11" กับความยาวก่อน "11" จะทำให้สแต็กว่างเปล่าอีกครั้ง ด้วยเหตุนี้ สตริง0 ⁿ 11 0 ⁿ 0 ⁿ 11 0 ⁿ ∈ L _pและ0 ⁿ 11 0 ⁿ 0 ^{n +2} 11 0 ^{n +2} ∉ L _pจึงไม่สามารถแยกแยะได้^{[ 4 ]}

การจำกัด DPDA ให้อยู่ในสถานะเดียวจะลดคลาสของภาษาที่ยอมรับเหลือเพียงภาษา LL(1) ^{[ 5 ]}ซึ่งเป็นคลาสย่อยที่เหมาะสมของ DCFL ^{[ 6 ]}ในกรณีของ PDA ข้อจำกัดนี้ไม่มีผลต่อคลาสของภาษาที่ยอมรับ

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

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

Géraud Sénizergues (1997) พิสูจน์ว่าปัญหาความเท่าเทียมกันสำหรับ PDA แบบกำหนด (เช่น กำหนด PDA แบบกำหนดสองตัว A และ B แล้ว L(A)=L(B) หรือไม่?) สามารถตัดสินได้^{[ 8 ] [ 9 ] [ 10 ]}ซึ่งเป็นการพิสูจน์ที่ทำให้เขาได้รับรางวัล Gödel Prize ประจำปี 2002 สำหรับ PDA แบบไม่กำหนด ความเท่าเทียมกันนั้นไม่สามารถตัดสินได้

• Hamburger, Henry; Dana S. Richards (2002). แบบจำลองตรรกะและภาษาสำหรับวิทยาศาสตร์คอมพิวเตอร์ . Upper Saddle River, NJ 07458: Prentice Hall. หน้า  284–331 . ISBN 0-13-065487-6.{{cite book}}: CS1 maint: location ( link )