X
On the trade-off between ambiguity and measures in internal contextual grammars
Kamala Krithivasan
Published in University of Prince Edward Island
2008
Pages: 216 - 223
Abstract
Several complexity measures and levels of ambiguity were defined for internal contextual grammars. In this paper, we consider the following trade-off between ambiguity and measures of these grammars. When a minimal complexity measure M1 is chosen for a language L, the corresponding grammar is ambiguous. Conversely, when an unambiguous grammar is chosen for L, the grammar is not minimal in M1. We introduce a new notion in formal language theory, named pseudo inherently ambiguous languages.