Title	การสร้างไวยากรณ์ไม่พึ่งบริบทแบบเชื่อมตรงโดยใช้ลำดับของกฎแฝง / สุรพงษ์ ผลประกอบศิลป์ = An on-line context-free grammars construction using sequences of hidden productions
Author	Surapong Phonprakobsin
Imprint	2550
Connect to	http://cuir.car.chula.ac.th/handle/123456789/13663
Descript	ง-ญ, 38 แผ่น : ภาพประกอบ

ในการวิเคราะห์และแก้ปัญหาด้านการอนุมานภาษาด้วยไวยากรณ์ไม่พึ่งบริบท งานวิจัยส่วนใหญ่จะมุ่งเน้นหาอัลกอริทึมเพื่อเรียนรู้และพัฒนาภาษาไวยากรณ์ไม่พึ่งบริบท จากการพิจารณาโครงสร้างของข้อมูลตัวอย่าง ซึ่งปัญหาที่พบคือ อัลกอริทึมส่วนใหญ่มีความซับซ้อนเชิงเชิงเวลาระดับเลขชี้กำลัง มีงานวิจัยของ วุฒิ สุนทรภัณฑ์ ที่สามารถอนุมานภาษาโดยใช้ความซับซ้อนเชิงเวลาระดับพหุนาม ซึ่งต้องอาศัยตัวอย่างลบในการลดทอนความกว้างของภาษาขณะเรียนรู้ ดังนั้นงานวิจัยนี้จึงเสนออัลกอริทึมสร้างไวยากรณ์ไม่พึ่งบริบทแบบใหม่ สำหรับบางภาษาไม่พึ่งบริบทรวมทั้งทุกภาษาสม่ำเสมอ ที่ใช้ความซับซ้อนเชิงเวลาระดับพหุนาม สามารถเรียนรู้ภาษาได้ด้วยจากตัวอย่างบวก ไม่จำเป็นต้องใช้ตัวอย่างลบ หลักการทำงานของอัลกอริทึม จะเริ่มสร้างไวยากรณ์ไม่พึ่งบริบทที่กว้างครอบคลุมทุกตัวอย่าง แล้วเรียนรู้รูปแบบลำดับของกฎแฝงให้อยู่ในรูปภาษาสม่ำเสมอ จะเห็นว่าลดความซับซ้อนเชิงเวลาน้อยกว่าเมื่อเทียบกับงานวิจัยอื่น และงานวิจัยของ วุฒิ สุนทรภัณฑ์ นอกจากนี้การทำงานของอัลกอริทึมเป็นแบบเชื่อมตรง คือสามารถเรียนรู้รูปแบบลำดับของกฎแฝงไปเรื่อยๆ เมื่อมีตัวอย่างใหม่เข้ามา
In an analysis and solving of grammar induction with context-free grammar, many researches focused on the algorithms that learned from considering the structure of data. The problem is that most algorithms have exponential time complexity. Wutthi Soonthonpant’s research can inference languages in polynomial time complexity, but needs negative examples to reduce the redundant of language during the learning process.Thus, this proposed research introduces a new construction algorithm for some context-free languages including all regular languages that has polynomial time complexity. This algorithm can be learned from only positive examples, with no need for negative examples. The concept of the algorithm is to initialize a general context-free grammar that covers all data, and learns sequences of hidden productions used in regular language. The time complexity of this algorithm is less than the other researches and Wutthi Soonthonpant’s research. In addition, The proposed algorithm also uses an on-line algorithm that can learn pattern of hidden productions in real-time, when receiving new input data.

LOCATION	CALL#	STATUS
Central Library @ Chamchuri 10 : Thesis	501092	LIB USE ONLY