## 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: Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)

C: Single tape turning machine and multi tape turning machine

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

**Question:**

The problem that is undecidable:

A: Membership problem for CFG’s

B: Ambiguity problem for CFG’s

C: Equivalence problem for FSA’s

D: Finiteness 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 odd length palindromes

D: All 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-complete

D: π is NP-hard but not 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 – X3 is recursively enumerable

B: X2 – X1 is recursively enumerable

C: X1 – X3 is recursively enumerable

D: X1 + 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 regular but not context free

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

D: It is not accepted by turing machine

**Question:**

The statement that holds true is:

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

B: Infinite union of finite sets is regular

C: Every subset of a regular set is 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 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 NP-complete

B: Both in P

C: NP-complete and in P respectively

D: Undecidable and NP-complete

**Question:**

Which one of the following statement is true?

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

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

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

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

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

C: 2k + 1

D: k + 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: Regular

D: Recursive

**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 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: (1 * 0) * 1*

B: None

C: (0 +1) * 10 (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

B: 2n

C: n + 1

D: n - 1

**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: Only S2 is correct

B: Only S1 is correct

C: Both S1 and S2 are correct

D: Neither S1 nor 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 for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}

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

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

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

**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: In Chomsky Normal Form the derivative trees of strings generated by a context-free grammar are always binary trees

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: Every left recursive grammar can be converted to a right recursive grammar and vice-versa

**Question:**

Which one of the following is true for this automaton?

A: b*ab*ab*

B: b*a(a+b)*

C: (a+b)*

D: b*ab*ab*ab*

## Recommended Other Related Topics

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

Triangles 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

Speed Time And Distance Online Exams MCQs Quiz Test

Time And Work Online Exams MCQs Quiz Test

Mathematics Online Exams MCQs Quiz Test