cs.FLcs.CLmath.LOmath.PR

Contributions to the hierarchy of probabilistic languages

📅 👥 2 authors arXiv:2609.23567v1

Authors

Abstract

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.

Paper Information

arXiv ID:
2609.23567v1
Published:

Related Categories

cs.FLcs.CLmath.LOmath.PR