Finite automata and non-self-embedding grammars
Marcella Anselmo, Dora Giammarresi, Stefano Varricchio · 2002
Abstract. We consider non-self-embedding (NSE) context-free grammars as a representation of regular sets. We point out its advantages with respect to more classical representations by finite automata, in particular when considering the efficient realization of the rational operations. We give a characterization in terms of composition of regular grammars and state relationships between NSE grammars and push-down automata. Finally we show a polynomial algorithm to decide whether a context-free grammars is self-embedding or not. 1