cs.FL — Formal Languages and Automata Theory
Nonstabilization of the Predictive Boolean Lookahead Hierarchy
We study the hierarchy of languages generated by predictive Boolean grammars. The model uses a deterministic recursive-descent table, strongly non-left-recursive rules, and at least one positive conjunct per rule. For every integer , we construct a language over a fixed eight-letter alphabet that has an ordinary grammar and establish that it has no predictive Boolean grammar. The construction asks for a specified token in a uniquely decodable word. The lower bound represents parsing on a long unary prefix by finitely many forward-moving endpoint streams and a finite Boolean recurrence. Random binary blocks followed by homogeneous blocks separate streams with a persistent timing error from streams having an exact finite-state potential. A bounded-lookahead argument hides a token-count change from each remaining stream. An encoding of the resulting independent queries is then shorter than their arbitrary binary payload. This gives nonstabilization under the stated predictive convention. The conclusion is for the stated parser model, including positive-conjunct and strong non-left-recursion requirements. Path-dependent tables satisfying these requirements give the same language families.