WCSE

Probabilistic Regular Grammar Inference Algorithm Using Incremental Technique

Abstract— 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 prefix tree. The algorithm starts by considering the shortest positive example. Two types of regular grammar rules (productions) are introduced. Our experimental results show that the probabilities obtained from our probabilistic finite state machine can be more accurate than the one obtained from the previous algorithm. We hope that our algorithm will be an alternative way for constructing a probabilistic finite state machine.

Index Terms— grammar inference, probabilistic finite state machine, incremental technique.

Torsak Penpinun, Athasit Surarerks
Department of Computer Engineering, Faculty of Engineering, Chulalongkorn University, THAILAND

[Download]

Cite: Torsak Penpinun, Athasit Surarerks, "Probabilistic Regular Grammar Inference Algorithm Using Incremental Technique," Proceedings of 2018 the 8th International Workshop on Computer Science and Engineering, pp. 780-785, Bangkok, 28-30 June, 2018.