Affiliations: Dipartimento di Informatica, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy. [email protected], [email protected]
Correspondence:
[*]
Address for correspondence: Dipartimento di Informatica, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy
Abstract: Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s.
Keywords: Context-free grammars, Descriptional complexity, Bounded languages
