BREADTH AND DEPTH GRAMMARS AND DEQUE AUTOMATA
Alessandra Cherubini, Claudio Citrini, Stefano Crespi Reghizzi, Dino Mandrioli · International Journal of Foundations of Computer Science · 1990
We introduce BD (Breadth-Depth) grammars which extend context-free grammars by allowing breadth-first derivations. Their languages are recognized by Deque (double ended queue) automata having a single state. BD languages also include languages recognized by monostatic queue automata. It is shown that the commutative image of BD languages is semilinear, that they have a periodicity (pumping) property, and can be homomorphically characterized as h(DAD∩R), where DAD is the Dyck-AntiDyck language, and R a regular set. Non-autoinclusive BD grammars coincide in power with breadth-first grammars with regular right parts.