SOURCE-LINKED INTELLIGENCE

Contributions to the hierarchy of probabilistic languages

arXiv · AI, language, vision and robotics · article · Sep 20, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global