Two-Dimensional Context-Free Grid Grammars

We expand upon the concept of context-free grammars into two dimensions with the introduction of the two-dimensional context-free grid grammar. In this model, production right-hand sides consist of general matrices containing both terminals and nonterminals. This proposal extends the Kolam array matrix grammar originally proposed by Siromoney et al. in 1973. By doing so, we provide a theoretical foundation for grammars frequently utilized in document analysis, highlighting both their capabilities and limitations. Our research reveals that the resulting family of picture languages possesses some properties not found in traditional one-dimensional context-free languages, a phenomenon commonly observed in the domain of picture languages.