Wikipedia: Wpc/decidable language

Difference (from prior major revision) (minor diff)

Changed: 6c6

does X belongs in the language?"

does X belong in the language?"

Changed: 9c9,10

* 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)

Changed: 12c13

None yet

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

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

Relevant Wikipedia Articles:

the concept- decidable language

related field(s)- theory of computation

potential real-world examples-

/Discussion?