Theory of Computation: Question Set – 27
Is the set of all context-free languages decidable?
No, the set of all context-free languages is not decidable. This can be shown using techniques such as the pumping lemma for context-free languages, or by reduction from an undecidable problem such as the halting problem.
Is the set of all regular languages decidable?
Yes, the set of all regular languages is decidable, meaning that there exists an algorithm that can determine whether any given language is regular or not. This can be done using techniques such as constructing a finite automaton that recognizes the language or using the pumping lemma to show that the language is not regular.
Can a language be undecidable but still computably enumerable?
Yes, it is possible for a language to be undecidable but still computably enumerable, meaning that there exists an algorithm that can list all the strings in the language, although it may not halt or produce an answer for strings that do not belong to the language. An example of such a language is the halting problem, which is undecidable but computably enumerable.
What is the difference between decidability and computability?
Decidability refers to whether a problem can be solved algorithmically, while computability refers to whether a function can be computed by an algorithm. Decidable problems can always be computed, while computable functions may not necessarily be decidable.
What is the difference between a context-sensitive grammar and a unrestricted grammar?
A context-sensitive grammar can generate context-sensitive languages, which are more powerful than context-free languages. Unrestricted grammars are the most powerful type of grammar and can generate all possible languages.
What is the difference between a turing decidable and a turing recognizable language?
A Turing decidable language is a language that can be decided by a Turing machine, which means there exists an algorithmic procedure that can determine whether any given input is in the language or not. A Turing recognizable language is a language that can be recognized by a Turing machine, which means there exists an algorithmic procedure that can accept any input in the language, but may loop forever on inputs that are not in the language.
What is the difference between a decidability problem and a complexity problem?
A decidability problem is one in which the goal is to determine whether a certain input satisfies a certain property or belongs to a certain language. A complexity problem is one in which the goal is to determine how efficiently a certain algorithm can solve a certain problem, usually measured in terms of time or space complexity.
What is the Cook-Levin theorem?
The Cook-Levin theorem states that the Boolean satisfiability problem (SAT) is NP-complete, which means that any problem in the NP complexity class can be reduced to SAT in polynomial time. This is one of the most important results in the theory of computation, as it shows that many important computational problems are intractable.