### SET 4

Question 1

**Let A be a problem that belongs to the class NP. Then which one of the following is TRUE?**

A : There is no polynomial time algorithm for A

B : If A can be solved deterministically in polynomial time,then P = NP

C : If A is NP-hard, then it is NP-complete

D : A may be undecidable

Answer Discuss it!

.

Correct answer is :C

Solution :

If a problem is both NP hard and NP, then it is NP Complete.

Question 2

**Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?**

A : The set of all strings containing the substring 00.

B : The set of all strings containing at most two 0’s

C : The set of all strings containing at least two 0’s.

D : The set of all strings that begin and end with either 0 or 1.

Answer Discuss it!

.

Correct answer is :C

Solution :

The regular expression has two 0?s surrounded by (0+1)* which means accepted strings must have at least 2 0?s.

Question 3

**Which one of the following is FALSE?**

A : There is unique minimal DFA for every regular language

B : Every NFA can be converted to an equivalent PDA

C : Complement of every context-free language is recursive

D : Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Answer Discuss it!

.

Correct answer is :D

Solution :

Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.

Question 4

**Let 1 2 L = L I L , where L1 ∩ L2 are languages as defined below:**

L1 = {a^{m}b^{m}ca^{n}b^{m} | m,n >= 0 }

L2={ a^{i}b^{j}c^{k} | i,j,k >= 0 }

Then L is

A : Not recursive

B : Regular

C : Context free but not regular

D : Recursively enumerable but not context free.

Answer Discuss it!

.

Correct answer is :C

Solution :

The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …}

L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }.

Intersection of these two languages is L1 cap L2 = {a^{k} b^{k} c | k >= 0} which is context free, but not regular.

Question 5

**The below DFA accepts the set of all strings over {0,1} that**

A : begin either with 0 or 1

B : end with 0

C : end with 00

D : contain the substring 00

Answer Discuss it!

.

Correct answer is :C

Question 6

**Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? **

(A) L2 - L1 is recursively enumerable.

(B) L1 – L3 is recursively enumerable

(C) L2 ∩ L1 is recursively enumerable

(D) L2 ∪ L1 is recursively enumerable

A : A

B : B

C : C

D : D

Answer Discuss it!

.

Correct answer is :B

Question 7

**Let L={w ∈ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?**

A : (0*10*1)*

B : 0*(10*10*)*

C : 0*(10*1*)*0*

D : 0*1(10*1)*10*

Answer Discuss it!

.

Correct answer is :B

Question 8

**Consider the languages **

L1 = {0^{i}1^{j} | i ≠ j}.

L2 = {0^{i}1^{j} | i = j}.

L3 = {0^{i}1^{j} | i = 2j+1}.

L4 = {0^{i}1^{j} | i != 2j}.

A : Only L2 is context free

B : Only L2 and L3 are context free

C : Only L1 and L2 are context free

D : All are context free

Answer Discuss it!

.

Correct answer is :D

Question 9

**Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?**

A : n-1

B : n

C : n+1

D : 2n-1

Answer Discuss it!

.

Correct answer is :C

Solution :

all the n states in the max length substring that is the string itself and one final state so n+1

Question 1

.

Correct answer is :C

Solution :

If a problem is both NP hard and NP, then it is NP Complete.

Question 2

.

Correct answer is :C

Solution :

The regular expression has two 0?s surrounded by (0+1)* which means accepted strings must have at least 2 0?s.

Question 3

.

Correct answer is :D

Solution :

Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.

Question 4

L1 = {a

^{m}b

^{m}ca

^{n}b

^{m}| m,n >= 0 }

L2={ a

^{i}b

^{j}c

^{k}| i,j,k >= 0 }

Then L is

.

Correct answer is :C

Solution :

The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …}

L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }.

Intersection of these two languages is L1 cap L2 = {a

^{k}b

^{k}c | k >= 0} which is context free, but not regular.

Question 5

.

Correct answer is :C

Question 6

(A) L2 - L1 is recursively enumerable.

(B) L1 – L3 is recursively enumerable

(C) L2 ∩ L1 is recursively enumerable

(D) L2 ∪ L1 is recursively enumerable

.

Correct answer is :B

Question 7

.

Correct answer is :B

Question 8

L1 = {0

^{i}1

^{j}| i ≠ j}.

L2 = {0

^{i}1

^{j}| i = j}.

L3 = {0

^{i}1

^{j}| i = 2j+1}.

L4 = {0

^{i}1

^{j}| i != 2j}.

.

Correct answer is :D

Question 9

.

Correct answer is :C

Solution :

all the n states in the max length substring that is the string itself and one final state so n+1