Consistency of stochastic context-free grammars
Computational linguistics play an important role in modeling various applications. Stochastic context-free grammars (SCFGs), for instance, are widely used in compiler testing, natural language processing (NLP), speech recognition and bioinformatics. The commonality of the former projects is that all require consistent SCFGs. This article addresses the consistency problem of SCFGs. We introduce a criterion for deciding the consistency and present a method for turning an inconsistent SCFG into consistent. The feasibility of our theory is demonstrated on random test data generation for some programming languages and formal notations. (C) 2010 Elsevier Ltd. All rights reserved.
consistency test data generation probabilistic grammar