Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Probabilistic Regular Grammar Inference Algorithm Using Incremental Technique
Year (A.D.)
2017
Document Type
Thesis
First Advisor
อรรถสิทธิ์ สุรฤกษ์
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิศวกรรมซอฟต์แวร์
DOI
10.58837/CHULA.THE.2017.1389
Abstract
การอนุมานไวยากรณ์เป็นเรื่องที่ได้รับการศึกษามาเป็นเวลานาน ซึ่งไวยากรณ์จะถูกแสดงในรูปของกฎการสร้างใหม่ ๆ พร้อมด้วยความน่าจะเป็นที่สนับสนุนกฎการสร้างไวยากรณ์นั้น งานวิจัยนี้สนใจในรูปแบบของไวยากรณ์ทั่วไปที่ได้รับการยอมรับผ่านเครื่องจักรแบบจำกัดสถานะ เทคนิคการอนุมานไวยากรณ์ที่ได้รับความนิยมในปัจจุบันคืออัลกอริทึมอัลเลอเจียร์ (Alergia) ซึ่งวิธีการคือสร้างเครื่องจักรแบบจำกัดสถานะเชิงความน่าจะเป็นจากตัวอย่างเชิงบวกพร้อมกับหาค่าความน่าจะเป็น ซึ่งงานวิจัยนี้นำเสนออัลกอริทึมการอนุมานไวยากรณ์เชิงความน่าจะเป็นจากการพิจารณาตัวอย่างเชิงบวกเริ่มต้นจากความยาวน้อยไปหาความยาวที่มากที่สุดตามลำดับ กำหนดรูปแบบให้กับไวยากรณ์ที่เกิดขึ้น และนำเสนอในรูปแบบของเครื่องจักรแบบจำลองสถานะเชิงความน่าจะเป็น
Other Abstract (Other language abstract of ETD)
Grammatical inference has been studied for a long time where grammar is illustrated by a collection of re-writing rules, together with their probabilities. We are interested in regular language model which can be recognized by a finite state machine. The most popular technique is an alergia algorithm. The objective is to construct a probabilistic finite state machine using only positive examples together with their probabilities (or frequency). In this work, we introduce a probabilistic grammatical inference algorithm in order to construct a finite state machine. The algorithm starts by considering the shortest positive example and generates two patterns of regular grammar rules (productions). Our experimental results show that the probabilities obtained from our probabilistic finite state machine can be more accurate than the one obtained from the alergia algorithm. Our algorithm is an alternative way for constructing a probabilistic finite state machine.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
เพ็ญภินันท์, ต่อศักดิ์, "อัลกอริทึมการอนุมานไวยากรณ์สม่ำเสมอเชิงความน่าจะเป็นด้วยเทคนิคการเพิ่มขึ้น" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 1879.
https://digital.car.chula.ac.th/chulaetd/1879