{"id":"arxiv/2609.23567","url":"https://arxiv.org/abs/2609.23567","tags":["cs.FL","cs.CL","math.LO","math.PR"],"score":0,"title":"Contributions to the hierarchy of probabilistic languages","domain":"cs.FL","source":"arxiv","authors":["Lothar Sebastian Krapp","Remo Nitschke"],"reviews":0,"subject":"cs.FL","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}