> > Mathematics MCQs > Computation Theory MCQs

Computation Theory MCQ

The problem, which is not NP-hard, is:

The 0/1 Knapsack problem

The graph colouring problem

Hamiltonian circuit problem

Finding bi-connected problem of a graph

Answer

Correct Answer: Hamiltonian circuit problem

Note: This Question is unanswered, help us to find answer for this one

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?

Both S1 and S2 are correct

Only S2 is correct

Neither S1 nor S2 is correct

Only S1 is correct

Answer

Correct Answer: Only S1 is correct

Note: This Question is unanswered, help us to find answer for this one

Which one of the following statement is true for the C language?

It is context-free language

It is a regular language

It is parsable fully only by a turing machine

It is context-sensitive language

Answer

Correct Answer: It is context-sensitive language

Note: This Question is unanswered, help us to find answer for this one

We have decision problems P1 and P2 as described below: P1: Does a given finite state machine accept a given string? P2: Does a given context-free grammar generate an infinite number of strings? The statement that holds true for P1 and P2 is:

Neither P1 nor P2 are decidable

Only P1 is decidable

Both P1 and P2 are decidable

Only P2 is decidable

Answer

Correct Answer: Both P1 and P2 are decidable

Note: This Question is unanswered, help us to find answer for this one

The last two symbols of L which is the set of all binary strings are same. In the minimum state deterministic finite state automaton, which is accepting L _____, states are present.

Answer

Correct Answer: 5

Note: This Question is unanswered, help us to find answer for this one

Let n be the length of a character string. How many substrings (of all lengths inclusive) can be formed from n?

(n (n+1)/2) + 1

N-1

N(n-1)/2

Answer

Correct Answer: (n (n+1)/2) + 1

Note: This Question is unanswered, help us to find answer for this one

The problem that is undecidable:

Membership problem for CFG’s

Equivalence problem for FSA’s

Finiteness problem for FSA’s

Ambiguity problem for CFG’s

Answer

Correct Answer: Ambiguity problem for CFG’s

Note: This Question is unanswered, help us to find answer for this one

Which one of the following statement is true?

The union of two context free languages is context free

The complement of a context free language is context free

The intersection of two context free languages is context free

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

Answer

Correct Answer: The union of two context free languages is context free

Note: This Question is unanswered, help us to find answer for this one

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

Single tape turning machine and multi tape turning machine

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

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

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

Answer

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

Note: This Question is unanswered, help us to find answer for this one

3-SAT and 2-SAT problems are:

Both in P

NP-complete and in P respectively

Both NP-complete

Undecidable and NP-complete

Answer

Correct Answer: NP-complete and in P respectively

Note: This Question is unanswered, help us to find answer for this one

Which one of the following is true for this automaton?

B*ab*ab*

B*a(a+b)*

B*ab*ab*ab*

(a+b)*

Answer

Correct Answer: B*a(a+b)*

Note: This Question is unanswered, help us to find answer for this one

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:

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

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

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

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

Answer

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

Note: This Question is unanswered, help us to find answer for this one

We have an undirected graph G(V, E) with two problems given below: α – Does G have an independent set of size IVI – 4? β – Does G have an independent set of size 5? The statement that holds true is:

Both α and β are NP-complete

α is NP-complete and β is in P

α is in P and β is NP-complete

Both α and β are in P

Answer

Correct Answer: α is in P and β is NP-complete

Note: This Question is unanswered, help us to find answer for this one

The set that can be recognized by a deterministic finite state automaton is:

The set of binary string in which the number of 0’s is same as the number of 1’s

The set {1, 101, 11011, 1110111, …….}

1, 2, 4, 8……2n ….. written in binary

1, 2, 4, 8……2n ….. written in unary

Answer

Correct Answer: 1, 2, 4, 8……2n ….. written in binary

Note: This Question is unanswered, help us to find answer for this one

Consider the language L = {W I W ∈ {0, 1}*, where 0’s and 1’s in W are divisible by 3 and 5 respectively. The minimum state deterministic finite automaton accepting the language L has:

15 states

10 states

5 states

20 states

Answer

Correct Answer: 15 states

Note: This Question is unanswered, help us to find answer for this one

Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is:

P3 is undecidable if P1 is reducible to P3

P3 is undecidable if P2 is reducible to P3

P3 is decidable if P3 is reducible to compliment of P2

P3 is decidable if P1 is reducible to P3

Answer

Correct Answer: P3 is undecidable if P2 is reducible to P3

Note: This Question is unanswered, help us to find answer for this one

The true regular expression is:

R(*) = r*

(r*s*)* = (r+s)*

R*s* = r* + s*

(r+s)* = r* + s*

Answer

Correct Answer: (r*s*)* = (r+s)*

Note: This Question is unanswered, help us to find answer for this one

Which one of the following is applicable for context free languages?

These are closed under complement, Kleene closure

These are closed under union, Kleene closure

These are closed under intersection, complement

These are closed under union, intersection

Answer

Correct Answer: These are closed under union, Kleene closure

Note: This Question is unanswered, help us to find answer for this one

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

All strings containing the substring 00

All strings containing at least two 0’s

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

All strings containing at least two 1’s

Answer

Correct Answer: All strings containing at least two 0’s

Note: This Question is unanswered, help us to find answer for this one

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

It is not regular but context free

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

It is not accepted by turing machine

It is regular but not context free

Answer

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

Note: This Question is unanswered, help us to find answer for this one

Computation Theory MCQ

The problem, which is not NP-hard, is:

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?

Which one of the following statement is true for the C language?

We have decision problems P1 and P2 as described below: P1: Does a given finite state machine accept a given string? P2: Does a given context-free grammar generate an infinite number of strings? The statement that holds true for P1 and P2 is:

The last two symbols of L which is the set of all binary strings are same. In the minimum state deterministic finite state automaton, which is accepting L _____, states are present.

Let n be the length of a character string. How many substrings (of all lengths inclusive) can be formed from n?

The problem that is undecidable:

Which one of the following statement is true?

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

3-SAT and 2-SAT problems are:

Which one of the following is true for this automaton?

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:

We have an undirected graph G(V, E) with two problems given below: α – Does G have an independent set of size IVI – 4? β – Does G have an independent set of size 5? The statement that holds true is:

The set that can be recognized by a deterministic finite state automaton is:

Consider the language L = {W I W ∈ {0, 1}*, where 0’s and 1’s in W are divisible by 3 and 5 respectively. The minimum state deterministic finite automaton accepting the language L has:

Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is:

The true regular expression is:

Which one of the following is applicable for context free languages?

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

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

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