## 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: Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA)

B: Single tape turning machine and multi tape turning machine

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

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

**Question:**

The problem that is undecidable:

A: Ambiguity problem for CFG’s

B: Finiteness problem for FSA’s

C: Membership problem for CFG’s

D: Equivalence problem for FSA’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 odd and even length palindromes

C: All even length palindromes

D: All odd 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 NP-hard but not NP-complete

B: π is neither NP-hard nor in NP

C: π is in NP 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: R is NP-hard

B: Q is NP-complete

C: R is NP-complete

D: Q is NP-hard

**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: X2 – X1 is recursively enumerable

B: X1 + X3 is recursively enumerable

C: X1 – X3 is recursively enumerable

D: X2 – X3 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 neither regular nor context free, but accepted by a turing machine

C: It is not accepted by turing machine

D: It is regular but not context free

**Question:**

The statement that holds true is:

A: Infinite union of finite sets is regular

B: Every subset of a regular set is regular

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

D: Every finite subset of a non-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 0’s

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

C: All strings containing at least two 1’s

D: All strings containing the substring 00

**Question:**

3-SAT and 2-SAT problems are:

A: Both in P

B: NP-complete and in P respectively

C: Both NP-complete

D: Undecidable and NP-complete

**Question:**

Which one of the following statement is true?

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

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

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

D: The union of two context free languages 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: n + 1

B: 2k + 1

C: k + 1

D: 2n + 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: Deterministic context free

B: Recursive

C: Context free

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 is not context free

B: L = 0+

C: L is context free but not regular

D: L is regular but not 0+

**Question:**

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

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

B: (1 * 0) * 1*

C: 0 + (0 + 10) *

D: None

**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: 2n

B: n + 1

C: n - 1

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: Both S1 and S2 are correct

B: Neither S1 nor S2 is 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)-n1(s) I ≤ 4

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) mod 7 = n1(s) mod 5 = 0}

**Question:**

Which one of the following statement is false?

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

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

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*ab*ab*

B: (a+b)*

C: b*ab*ab*ab*

D: b*a(a+b)*

## 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

Easy Mathematics Online Exams MCQs Quiz Test

Number Series Completion Online Exams MCQs Quiz Test

Pie Chart Online Exams MCQs Quiz Test

Time And Work Online Exams MCQs Quiz Test

Mathematics Online Exams MCQs Quiz Test

Speed Time And Distance Online Exams MCQs Quiz Test