Q.1 Which of the following is considered the father of Theory of Computation?
Alan Turing
Alonzo Church
John von Neumann
Claude Shannon
Explanation - Alan Turing introduced the concept of Turing Machines, which is foundational to the Theory of Computation.
Correct answer is: Alan Turing
Q.2 What is the main purpose of a Turing Machine?
To perform calculations quickly
To recognize languages
To store large amounts of data
To communicate over networks
Explanation - Turing Machines are abstract models used to recognize or decide formal languages, illustrating what can be computed.
Correct answer is: To recognize languages
Q.3 Which of the following is NOT a type of formal language?
Regular Language
Context-Free Language
Context-Sensitive Language
Binary Language
Explanation - Binary is a representation system, not a formal language type in computation theory.
Correct answer is: Binary Language
Q.4 Which automaton is used to recognize regular languages?
Finite Automaton
Pushdown Automaton
Linear Bounded Automaton
Turing Machine
Explanation - Finite Automata are specifically designed to recognize regular languages.
Correct answer is: Finite Automaton
Q.5 What type of grammar generates context-free languages?
Regular Grammar
Context-Free Grammar
Context-Sensitive Grammar
Unrestricted Grammar
Explanation - Context-Free Grammar (CFG) generates context-free languages, which are recognized by Pushdown Automata.
Correct answer is: Context-Free Grammar
Q.6 Which statement best describes the Church-Turing Thesis?
Every problem can be solved by a Turing Machine
Every effectively computable function can be computed by a Turing Machine
Turing Machines are faster than any real computer
All algorithms are finite
Explanation - The Church-Turing Thesis asserts that anything computable by an algorithm can be computed by a Turing Machine.
Correct answer is: Every effectively computable function can be computed by a Turing Machine
Q.7 Which of the following languages is NOT necessarily regular?
{a^n b^n | n ≥ 0}
{0,1}*
{a|b}*
{abb}
Explanation - The language {a^n b^n | n ≥ 0} requires counting and is context-free, not regular.
Correct answer is: {a^n b^n | n ≥ 0}
Q.8 Which automaton has memory in the form of a stack?
Finite Automaton
Pushdown Automaton
Turing Machine
DFA
Explanation - Pushdown Automata use a stack to store information, which allows them to recognize context-free languages.
Correct answer is: Pushdown Automaton
Q.9 What does a Linear Bounded Automaton (LBA) recognize?
Regular Languages
Context-Free Languages
Context-Sensitive Languages
All languages
Explanation - LBAs recognize context-sensitive languages, which are more powerful than context-free languages but limited compared to Turing Machines.
Correct answer is: Context-Sensitive Languages
Q.10 Which is an example of an undecidable problem?
Determining if a DFA accepts a string
The Halting Problem
Checking if a string is in a regular language
Parsing a context-free grammar
Explanation - The Halting Problem, which asks whether a Turing Machine halts on input, is undecidable.
Correct answer is: The Halting Problem
Q.11 What is the language recognized by a DFA with a single state that is both start and accepting?
Empty language
All strings over the alphabet
Single-character strings
Infinite strings only
Explanation - If the single state is accepting, any string processed will be accepted, representing the full language over the alphabet.
Correct answer is: All strings over the alphabet
Q.12 Which of the following is true about Non-deterministic Finite Automata (NFA)?
NFAs can recognize languages DFAs cannot
NFAs and DFAs recognize the same class of languages
NFAs are less powerful than DFAs
NFAs cannot be converted to DFAs
Explanation - Although NFAs allow multiple transitions, they recognize exactly the regular languages, same as DFAs.
Correct answer is: NFAs and DFAs recognize the same class of languages
Q.13 Which notation is commonly used to represent regular expressions?
CFG Notation
Regex Syntax
BNF
LBA Representation
Explanation - Regular expressions use specific syntax to describe patterns in regular languages.
Correct answer is: Regex Syntax
Q.14 What is the significance of the Pumping Lemma for regular languages?
It proves all languages are regular
It is used to test whether a language is regular
It generates context-free languages
It converts NFA to DFA
Explanation - The Pumping Lemma provides a property all regular languages satisfy, helping to prove some languages are not regular.
Correct answer is: It is used to test whether a language is regular
Q.15 Which of the following is true about context-sensitive grammars?
They generate only regular languages
Their productions can have the form αAβ → αγβ
They are less powerful than context-free grammars
They can be recognized by DFA
Explanation - Context-sensitive grammars allow rules where non-terminals can be replaced by strings depending on surrounding context.
Correct answer is: Their productions can have the form αAβ → αγβ
Q.16 Which of the following models is most powerful in terms of language recognition?
DFA
NFA
PDA
Turing Machine
Explanation - Turing Machines can recognize recursively enumerable languages, which are more powerful than regular, context-free, or context-sensitive languages.
Correct answer is: Turing Machine
Q.17 Which problem is decidable?
The Halting Problem
Checking equivalence of two DFAs
Post Correspondence Problem
Determining if a Turing Machine accepts a string
Explanation - Equivalence of two DFAs is a decidable problem because DFAs have finite states and can be systematically compared.
Correct answer is: Checking equivalence of two DFAs
Q.18 Which of the following is NOT true about recursive languages?
They are decidable
They can be recognized by a Turing Machine that always halts
They include some context-sensitive languages
All recursive languages are undecidable
Explanation - Recursive languages are, by definition, decidable. Some context-sensitive languages are also recursive.
Correct answer is: All recursive languages are undecidable
Q.19 What is a distinguishing feature of a nondeterministic Turing Machine?
It has multiple heads
It can move its head both left and right
It can choose among multiple possible moves at each step
It always halts
Explanation - A nondeterministic Turing Machine can follow multiple possible transitions at each step, unlike deterministic Turing Machines.
Correct answer is: It can choose among multiple possible moves at each step
Q.20 Which of the following is a subset of context-free languages?
Regular Languages
Context-Sensitive Languages
Recursively Enumerable Languages
All languages
Explanation - Regular languages are a subset of context-free languages because any regular grammar can be expressed as a context-free grammar.
Correct answer is: Regular Languages
Q.21 Which language class is recognized by a Turing Machine that may not halt on all inputs?
Recursive Languages
Recursively Enumerable Languages
Regular Languages
Context-Free Languages
Explanation - Recursively enumerable languages are those where a Turing Machine will accept strings in the language but may not halt on strings outside it.
Correct answer is: Recursively Enumerable Languages
Q.22 Which of the following is true about Chomsky Hierarchy?
Regular < Context-Free < Context-Sensitive < Recursively Enumerable
Context-Free < Regular < Context-Sensitive < Recursively Enumerable
Recursively Enumerable < Context-Sensitive < Context-Free < Regular
Regular = Context-Free = Context-Sensitive = Recursively Enumerable
Explanation - The Chomsky hierarchy arranges language classes by increasing expressive power.
Correct answer is: Regular < Context-Free < Context-Sensitive < Recursively Enumerable
Q.23 Which of the following statements is true about DFA minimization?
Every DFA can be minimized to a unique smallest DFA
Minimization is impossible for some DFAs
Only NFAs can be minimized
DFA minimization changes the language it accepts
Explanation - Every DFA has a unique minimal equivalent DFA with the smallest number of states accepting the same language.
Correct answer is: Every DFA can be minimized to a unique smallest DFA
Q.24 Which of the following is true for a language and its complement?
If a language is regular, its complement is also regular
If a language is context-free, its complement is always context-free
If a language is context-sensitive, its complement is undecidable
Complement operation is only defined for regular languages
Explanation - Regular languages are closed under complementation; the complement of a regular language is also regular.
Correct answer is: If a language is regular, its complement is also regular