NationMaster - Encyclopedia: Decidable language

In computer science a formal language is called recursive or decidable if there exists an algorithm to decide for any given string w over the alphabet of the language, if w belongs to the language or not.

More formally, a formal language is called recursive if and only if it is a recursive subset in the set of all possible words over the alphabet of the language.

All regular, context-free and context-sensitive languages are recursive.

Categories: Formal languages | Computability

Results from FactBites:

algorithm (1146 words)
	The associated language is called a decidable language or a recursive language.
	A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps --- equivalently can be recognized by a Turing machine that halts for all inputs.
	DS associates each language statement with a function dsem from the state of the program before the execution to the state after execution.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m