โดยอัตโนมัติแบบเลื่อนลงสามารถใช้สองภาษาได้ (หรือเงื่อนไข)
ในการทำการบ้านเราต้องสร้างระบบอัตโนมัติแบบเลื่อนลงสำหรับ 2 ภาษา แต่ในความคิดของฉันนี่เป็นแบบฝึกหัดสองแบบที่หุ่นยนต์เหมือนกันสำหรับทั้งสองอย่าง
ตามที่ฉันเข้าใจเราสามารถสร้างระบบอัตโนมัติแบบกดลงที่ไม่ได้กำหนดได้และทุกครั้งที่เราอ่านอักขระ a เราสามารถแทรก A ตัวเดียวหรือสองตัวได้ - ขึ้นอยู่กับ 'ดุลยพินิจ' ของออโตเมตัน
จากนั้นสถานะจะถูกสร้างขึ้นสำหรับอักขระ b ซึ่งทุกครั้งที่เขาอ่าน A เขาจะดึงมันออกจากสแต็ก ด้วยวิธีนี้หุ่นยนต์จะรู้วิธีจัดการทั้งสองภาษาโดยที่จำนวน a เท่ากับจำนวน b และภาษาที่ชอบ a เป็นสองเท่าของจำนวน b
ฉันถูกไหม? หรือฉันขาดอะไรไป?
ถ้าไม่ฉันอยากจะเข้าใจวิธีจัดการกับภาวะ“ หรือ” ในการออกกำลังกายครั้งแรก
ขอขอบคุณ.
คำตอบ
ตั้งแต่ $L_2\ne L_3$พวกเขาไม่สามารถยอมรับได้อย่างชัดเจนโดยอัตโนมัติแบบเลื่อนลงเดียวกัน ดูเหมือนว่าคุณจะนึกถึงหุ่นยนต์ที่จดจำได้$L_3$. อาจเป็นวิธีที่ง่ายที่สุดในการออกแบบให้จดจำได้$L_2$คือการออกแบบออโตมาตาแบบเลื่อนลงที่กำหนดไว้สองตัวสำหรับ $\{a^nb^n:n\in\Bbb N\}$ และอีกอันสำหรับ $\{a^{2n}b^n:n\in\Bbb N\}$. จากนั้นรวมเข้าด้วยกันเป็นระบบอัตโนมัติแบบเลื่อนลงเครื่องเดียวที่มีการเปลี่ยน$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ และ $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, ที่ไหน $q_0$ เป็นสถานะเริ่มต้นของ PDA รวม $Z$ คือสัญลักษณ์สแต็กเริ่มต้นและ $q_1$ และ $q_2$เป็นสถานะเริ่มต้นของออโตมาตาแบบเลื่อนลงในเครือทั้งสอง กล่าวอีกนัยหนึ่งสิ่งแรกที่ PDA รวมทำคือ 'เลือก' ว่าจะค้นหาคำประเภทใด$a^nb^n$ หรือคำประเภท $a^{2n}b^n$จากนั้นก็ดำเนินการตามทางเลือกนั้นอย่างกำหนด