Degree-languages: A new concept of acceptance

摘要

The concept of acceptance degree is introduced. A string is accepted by a recognition device if and only if its acceptance degree is not less than a preselected rational number. A degree-language is the set of all those strings. The class of degree-languages over push-down automata (linear bounded automata) contains the intersection-closure and the complements of the context-free (context-sensitive) languages and it is contained in the Boolean closure of the context-free (context-sensitive) languages. Consequently degree-languages over pushdown automata can be recognized as fast as context-free languages. The class of context-sensitive languages is closed under complementation if and only if every degree-language over a linear bounded automaton is either context-sensitive or is the complement of a context-sensitive language.