Decidable languages and problems MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

xDecidable Languages and Problems
Which of the following best defines a decidable language?

A) A language for which there exists an algorithm that accepts all strings in the language and rejects all strings not in the language.
B) A language that is regular.
C) A language that can be recognized by a non-deterministic Turing machine.
D) A language that contains only finite strings.
Answer: A

The halting problem is:

A) Decidable
B) Undecidable
C) Regular
D) Context-free
Answer: B

Which of the following is an example of a decidable problem?

A) Determining whether a given Turing machine accepts an infinite language.
B) Determining whether a given context-free grammar is ambiguous.
C) Determining whether a given DFA accepts a given string.
D) Determining whether a given regular expression generates a context-free language.
Answer: C

A decidable problem is one for which:

A) There exists an algorithm that always terminates and correctly answers “yes” or “no”.
B) There exists a Turing machine that can accept the problem in finite time.
C) There exists a non-deterministic Turing machine that can always solve the problem.
D) There exists a context-sensitive grammar that generates the language.
Answer: A

The language L = {0^n 1^n | n ≥ 0} is:

A) Decidable
B) Undecidable
C) Regular
D) Context-free
Answer: A

Which of the following is a decidable problem related to context-free languages?

A) Determining whether two context-free grammars generate the same language.
B) Determining whether a given Turing machine accepts an infinite language.
C) Determining whether a given regular expression generates a context-sensitive language.
D) Determining whether a given DFA accepts all strings.
Answer: A

The set of all decidable languages is closed under which of the following operations?

A) Union
B) Intersection
C) Complementation
D) Kleene star
Answer: A

Which of the following problems is undecidable?

A) Checking whether a given Turing machine halts on all inputs.
B) Checking whether a given regular expression generates an infinite language.
C) Checking whether a given context-free grammar is ambiguous.
D) Checking whether a given DFA accepts all strings.
Answer: A

The language L = {a^n b^n c^n | n ≥ 0} is:

A) Decidable
B) Undecidable
C) Regular
D) Context-free
Answer: B

A problem is decidable if:

A) It can be solved using a Turing machine with infinite tape.
B) It can be solved in polynomial time.
C) There exists an algorithm that always halts and gives the correct answer.
D) It can be reduced to a context-free language.
Answer: C

 

Related Posts: