## Theory Of Computation IQ Test Quiz Instructions:

**20**.

## Theory Of Computation Quiz Test Questions and Options:

**Question:**

From the options given below, the pair having different expressive power is:

A: Single tape turning machine and multi tape turning machine

B: Deterministic single tape turning machine and Non-Deterministic single tape turning machine

C: Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)

D: Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA)

**Question:**

The problem that is undecidable:

A: Equivalence problem for FSA’s

B: Ambiguity problem for CFG’s

C: Finiteness problem for FSA’s

D: Membership problem for CFG’s

**Question:**

The language which is generated by the grammar S-> aSa I bSb I a I b over the alphabet {a, b} is the set of:

A: Strings that begin and end with the same symbol

B: All even length palindromes

C: All odd length palindromes

D: All odd and even length palindromes

**Question:**

Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that:

A: π is neither NP-hard nor in NP

B: π is in NP but not NP-complete

C: π is NP-hard but not NP-complete

D: π is NP-complete

**Question:**

Out of the three problems S, Q and R, S is an NP-complete problem and Q and R are the two other problems not known to be in NP. Which one of the following statements is true if Q is polynomial time reducible to S and S is the polynomial time reducible to R?

A: Q is NP-complete

B: R is NP-hard

C: Q is NP-hard

D: R is NP-complete

**Question:**

From the options given below the statement, which is not necessarily true if X1 is the recursive language and X2 and X3 are the languages that is recursively enumerable but not recursive is:

A: X1 + X3 is recursively enumerable

B: X1 – X3 is recursively enumerable

C: X2 – X3 is recursively enumerable

D: X2 – X1 is recursively enumerable

**Question:**

For the language {ap I P is a prime}, the statement which hold true is

A: It is not regular but context free

B: It is regular but not context free

C: It is not accepted by turing machine

D: It is neither regular nor context free, but accepted by a turing machine

**Question:**

The statement that holds true is:

A: Infinite union of finite sets is regular

B: Every finite subset of a non-regular set is regular

C: The union of two non-regular set is not regular

D: Every subset of a regular set is regular

**Question:**

The language described by the regular expression (0+1)*0(0+1)*0(0+1)* over the alphabet {0 1} is the set of:

A: All strings containing at least two 1’s

B: All strings containing at least two 0’s

C: All strings containing the substring 00

D: All strings that begin and end with either 0’s or 1’s

**Question:**

3-SAT and 2-SAT problems are:

A: Both in P

B: NP-complete and in P respectively

C: Undecidable and NP-complete

D: Both NP-complete

**Question:**

Which one of the following statement is true?

A: A context free language can always be accepted by a deterministic push down automaton

B: The intersection of two context free languages is context free

C: The union of two context free languages is context free

D: The complement of a context free language is context free

**Question:**

Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be:

A: k + 1

B: n + 1

C: 2n + 1

D: 2k + 1

**Question:**

Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as:

A: Context free

B: Deterministic context free

C: Recursive

D: Regular

**Question:**

Which one of the following statement is true if L denotes the language generated by the grammar S->0S0/00?

A: L = 0+

B: L is not context free

C: L is regular but not 0+

D: L is context free but not regular

**Question:**

Consider the regular expression 0 * (10 *) which is similar to the same set as:

A: None

B: (0 +1) * 10 (0 + 1) *

C: (1 * 0) * 1*

D: 0 + (0 + 10) *

**Question:**

W is any string whose length is n in {0, 1}* and L is the set of all sub-strings of W. The minimum number of states in a non-deterministic finite automaton that accepts L is:

A: n + 1

B: n - 1

C: 2n

D: N

**Question:**

We have two statements S1 and S2 whose definition are as follows:

S1 – {02n In ≥ I} is a regular language.

S2 – {0m 1n 0 1m+n Im=1 and n≥1I is a regular language.

Which one of the following statements is correct?

A: Neither S1 nor S2 is correct

B: Both S1 and S2 are correct

C: Only S1 is correct

D: Only S2 is correct

**Question:**

Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is:

A: L = {s ∈ (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}

B: L = {s ∈ (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}

C: L = {s ∈ (0+1)* I no(s) is a 3 digit prime}

D: L = {s ∈ (0+1)* I no(s)-n1(s) I ≤ 4

**Question:**

Which one of the following statement is false?

A: By using suitable transformation all ε-productions can be removed from any context-free grammar

B: Every left recursive grammar can be converted to a right recursive grammar and vice-versa

C: If W is the string of a terminals and Y is a non-terminal, the language generated by a context free grammar, all of whose productions are of the form x->W or X->WY is always regular

D: In Chomsky Normal Form the derivative trees of strings generated by a context-free grammar are always binary trees

**Question:**

Which one of the following is true for this automaton?

A: b*a(a+b)*

B: (a+b)*

C: b*ab*ab*

D: b*ab*ab*ab*

## Recommended Other Related Topics

D-Block Elements Test Online Exams MCQs Quiz TestTriangles Online Exams MCQs Quiz Test

Logical Online Exams MCQs Quiz Test

Ionic Equilibria Test Online Exams MCQs Quiz Test

Number Series Completion Online Exams MCQs Quiz Test

Easy Mathematics Online Exams MCQs Quiz Test

Time And Work Online Exams MCQs Quiz Test

Pie Chart Online Exams MCQs Quiz Test

Line Chart Online Exams MCQs Quiz Test

Speed Time And Distance Online Exams MCQs Quiz Test