ภาษาที่ไม่มีบริบทสามารถตัดสินใจได้หรือไม่?

2024 ผู้เขียน: Fiona Howard | [email protected]. แก้ไขล่าสุด: 2024-01-10 06:43

1. (a) จริง เนื่องจากทุกภาษาปกติไม่มีบริบท ทุกภาษาที่ไม่มีบริบทสามารถตัดสินใจได้ และทุกภาษาที่ตัดสินใจได้คือ Turing-recognizable

ทำไมจึงเลือกภาษาที่ไม่มีบริบทได้

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

เซตย่อยของภาษาที่ไม่มีบริบทกำหนดได้หรือไม่

2 คำตอบ. Σ ไม่มีบริบท (ปกติคือปกติ) และมีชุดย่อยมากมาย ถ้า L เป็นภาษาที่ไม่มีบริบทซึ่งมีขนาดไม่สิ้นสุด ก็จะมีชุดย่อย J ของ L ที่ตัดสินใจได้ และบางส่วนก็ไม่สามารถตัดสินใจได้ ตัวอย่างเช่น เซตย่อยว่างสามารถกำหนดได้

CFL ตัดสินได้หรือไม่

CFL: ตัดสินใจได้สำหรับปัญหาความว่างเปล่า ปัญหาความจำกัด และปัญหาการเป็นสมาชิก.

ไม่มีบริบทกี่ภาษา

(1) มี จำนวนภาษาที่ไม่มีบริบทนับไม่ถ้วน สิ่งนี้เป็นจริงเพราะทุกคำอธิบายของภาษาที่ไม่มีบริบทมีความยาวจำกัด ดังนั้นจึงมีคำอธิบายดังกล่าวจำนวนนับไม่ถ้วน (2) มีภาษามากมายนับไม่ถ้วน