Restricted Minimal Linear Languages: A Formal Characterization of $\text{AC}^{0}$

We introduce Restricted Minimal Linear Languages (RmLIN), a syntactically constrained subclass of context-free languages defined by fixed-context, recursive rules with a single non-terminal. Despite their simplicity, RmLIN grammars generate non-regular languages such as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\left\{a^{n} b^{n}\right\}$</tex>, while provably excluding counting-based languages like Parity and Majority. We define an automaton model, the Restricted Context-Matching Two-Head Automaton (RCM-2HA), that characterizes RmLIN. Crucially, we prove that the class of languages generated by RmLIN grammars is exactly the class <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{A C}^{0}$</tex> - constant-depth, polynomial-size Boolean circuits. This syntactic characterization of a semantic complexity class bridges formal language theory with circuit complexity and opens new avenues for low-level computation analysis.