# Contributions to the hierarchy of probabilistic languages

arXiv: https://arxiv.org/abs/2609.23567 · HTML: https://mlsanity.com/paper/2609.23567/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 13 references that are in the map.
- First posted on arXiv 20 Sep 2026.

## Abstract (arXiv)

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.