<<Up     Contents

Redirected from Wpc/decidable language

Table of contents 1 Also known as: 2 Definition: 3 Generalizations: 4 Specializations: 5 Involved in: 6 Relevant Wikipedia Articles:

Also known as:

Recursive language

Definition:

A formal language for which the following problem is decidable: "Given string X, does X belong in the language?"

Generalizations:

• enumerable language (don't require that the algorithm stop on strings that don't belong in the language)
• co-enumerable language[?] (complement of an enumerable language)

Specializations:

• context-free language (accepted by a pushdown automaton)

Involved in:

Nothing yet