### SET 6

Question 1

**Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?**

A : P3 is decidable if P1 is reducible to P3

B : P3 is undecidable if P3 is reducible to P2

C : P3 is undecidable if P2 is reducible to P3

D : P3 is decidable if P3 is reducible to P2's complement

Answer Discuss it!

.

Correct answer is :C

Question 2

**Consider the machine M: The language recognized by M is:**

A : {w ∈ {a, b}* / every a in w is followed by exactly two b's}

B : {w ∈ {a, b}* every a in w is followed by at least two b’}

C : {w ∈ {a, b}* w contains the substring 'abb'}

D : {w ∈ {a, b}* w does not contain 'aa' as a substring}

Answer Discuss it!

.

Correct answer is :B

Solution :

We can try some sample strings like aba, abbbb, abbbabbb

Question 3

**Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?**

A : Df ⊂ Nf and Dp ⊂ Np

B : Df ⊂ Nf and Dp = Np

C : Df = Nf and Dp = Np

D : Df = Nf and Dp ⊂ Np

Answer Discuss it!

.

Correct answer is :D

Solution :

Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design. Deterministic context-free languages (DCFL) are a proper subset of context-free languages. Non-deterministic finite automata and Deterministic finite automata, both accept same set of languages as NFAs can be translated to equivalent DFAs using the subset construction algorithm.

Question 4

**Consider the languages: **

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

L2 = {a^{n}b^{m}c^{m} | n, m > 0}

Which one of the following statements is FALSE?

A : L1 ∩ L2 is a context-free language

B : L1 U L2 is a context-free language

C : L1 and L2 are context-free language

D : L1 ∩ L2 is a context sensitive language

Answer Discuss it!

.

Correct answer is :A

Solution :

L1 and L2 are context free languages. See this for closure properties.

Question 5

**Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE? **

L1' --> Complement of L1

L2' --> Complement of L2

A : L1' is recursive and L2' is recursively enumerable

B : L1' is recursive and L2' is not recursively enumerable

C : L1' and L2' are recursively enumerable

D : L1' is recursively enumerable and L2' is recursive

Answer Discuss it!

.

Correct answer is :B

Solution :

Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. Recursive Languages are closed under complementation, but recursively enumerable are not closed under complementation. If a languages L is recursively enumerable, then the complement of it is recursively enumerable if and only if L is also recursive. Since L2 is recursively enumerable, but

Question 6

**Consider the languages:**

L1 = {ww^{R} |w ∈ {0, 1}*}

L2 = {w#w^{R} | w ∈ {0, 1}*}, where # is a special symbol

L3 = {ww | w ∈ (0, 1}*)

Which one of the following is TRUE?

A : L1 is a deterministic CFL

B : L2 is a deterministic CFL

C : L3 is a CFL, but not a deterministic CFL

D : L3 is a deterministic CFL

Answer Discuss it!

.

Correct answer is :B

Question 7

**Consider the following two problems on undirected graphs **

α : Given G(V, E), does G have an independent set of size | V | - 4?

β : Given G(V, E), does G have an independent set of size 5?

Which one of the following is TRUE?

A : α is in P and β is NP-complete

B : α is NP-complete and β is in P

C : Both α and β are NP-complete

D : Both α and β are in P

Answer Discuss it!

.

Correct answer is :C

Solution :

Graph independent set decision problem is NP Complete.

Question 8

**The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE?**

A : It computes 1's complement of the input number

B : It computes 2's complement of the input number

C : It increments the input number

D : It decrements the input number

Answer Discuss it!

.

Correct answer is :B

Question 9

**Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? A**

A : R is NP-complete

B : R is NP-hard

C : Q is NP-complete

D : Q is NP-hard

Answer Discuss it!

.

Correct answer is :B

Solution :

(A) Incorrect because R is not in NP. A NP Complete problem has to be in both NP and NP-hard.

(B) Correct because a NP Complete problem S is polynomial time educable to R.

(C) Incorrect because Q is not in NP.

(D) Incorrect because there is no NP-complete problem that is polynomial time Turing-reducible to Q.

Question 10

**Let L1={ 0**^{n+m}1^{n}0^{m} | n,m>=0 } , L2={ 0^{n+m}1^{n+m}0^{m} | n,m>=0 } and L3={ 0^{n+m}1^{n+m}0^{n+m} | n,m>=0 }

Which of these languages are NOT context free?

A : L1 only

B : L3 only

C : L1 and L2

D : L2 and L3

Answer Discuss it!

.

Correct answer is :D

Solution :

A PDA can be built only for L1. It is not possible to build PDA for L2 and L3.

Question 11

**If s is a string over (0 + 1)* then let n0(s) denote the number of 0’s in s and n1(s) the number of 1’s in s. Which one of the following languages is not regular?**

A : L ={ s ∈ (0 + 1) * | n0 (s) is a 3-digit prime }

B : L ={ s ∈ (0 + 1) * | for every prefix s` of s1 | n0(s`)-n1(s`) <=2 }

C : L ={ s ∈ (0 + 1) * | n0 (s) - n1(s) | <=4 }

D : L ={ s ∈ (0 + 1) * | n0 (s) mod 7 = n1(s) mod 5 =0 }

Answer Discuss it!

.

Correct answer is :B

Solution :

Languages in option (A) And (D) are finite so both the options are eliminated. Only left options are (B) and (C). Both (B) and (C) look not regular as we don't have memory in DFA.

Question 12

**For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s) mod 5 = 2 and d(s) mod 7 != 4}. Which one of the following statements is true?**

A : L is recursively enumerable, but not recursive

B : L is recursive, but not context-free

C : L is context-free, but not regular

D : L is regular

Answer Discuss it!

.

Correct answer is :D

Solution :

It is regular L1=d(s) mod 5 =2 is regular with 5 states L2=d(s) mod 7 =4 is regular with 7 states therefore L1 ^ L2' should be regular because regular grammar are closed under intersection and compliment

Question 13

**Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?**

A : Both DHAM3 and SHAM3 are NP-hard

B : SHAM3 is NP-hard, but DHAM3 is not

C : DHAM3 is NP-hard, but SHAM3 is not

D : Neither DHAM3 nor SHAM3 is NP-hard

Answer Discuss it!

.

Correct answer is :A

Question 14

**Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?**

A : L1 ∩ L2 is a deterministic CFL

B : L3 ∩ L1 is recursive

C : L1 ∪ L2 is context free

D : L1 ∩ L2 ∩ L3 is recursively enumerable

Answer Discuss it!

.

Correct answer is :B

Question 15

**Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:**

A : 3

B : 5

C : 8

D : 9

Answer Discuss it!

.

Correct answer is :D

Question 16

**Which one of the following grammars generates the language L = {a**^{i}b^{j} | i ≠ j}

A : S->AC|CB

C->aCb|a|b

A->aA | ε

B-> Bb|ε

B : S -> aS|Sb|a|b

C : S->AC|CB

C->aCb|&epsioln;

A->aA | ε

B-> Bb|ε

D : S->AC|CB

C->aCb|&epsioln;

A->aA | a

B-> Bb|b

Answer Discuss it!

.

Correct answer is :D

Question 1

.

Correct answer is :C

Question 2

.

Correct answer is :B

Solution :

We can try some sample strings like aba, abbbb, abbbabbb

Question 3

.

Correct answer is :D

Solution :

Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design. Deterministic context-free languages (DCFL) are a proper subset of context-free languages. Non-deterministic finite automata and Deterministic finite automata, both accept same set of languages as NFAs can be translated to equivalent DFAs using the subset construction algorithm.

Question 4

L1 = {a

^{n}b

^{n}c

^{m}| n, m > 0}

L2 = {a

^{n}b

^{m}c

^{m}| n, m > 0}

Which one of the following statements is FALSE?

.

Correct answer is :A

Solution :

L1 and L2 are context free languages. See this for closure properties.

Question 5

L1' --> Complement of L1

L2' --> Complement of L2

.

Correct answer is :B

Solution :

Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. Recursive Languages are closed under complementation, but recursively enumerable are not closed under complementation. If a languages L is recursively enumerable, then the complement of it is recursively enumerable if and only if L is also recursive. Since L2 is recursively enumerable, but

Question 6

L1 = {ww

^{R}|w ∈ {0, 1}*}

L2 = {w#w

^{R}| w ∈ {0, 1}*}, where # is a special symbol

L3 = {ww | w ∈ (0, 1}*)

Which one of the following is TRUE?

.

Correct answer is :B

Question 7

α : Given G(V, E), does G have an independent set of size | V | - 4?

β : Given G(V, E), does G have an independent set of size 5?

Which one of the following is TRUE?

.

Correct answer is :C

Solution :

Graph independent set decision problem is NP Complete.

Question 8

.

Correct answer is :B

Question 9

.

Correct answer is :B

Solution :

(A) Incorrect because R is not in NP. A NP Complete problem has to be in both NP and NP-hard.

(B) Correct because a NP Complete problem S is polynomial time educable to R.

(C) Incorrect because Q is not in NP.

(D) Incorrect because there is no NP-complete problem that is polynomial time Turing-reducible to Q.

Question 10

^{n+m}1

^{n}0

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

^{n+m}1

^{n+m}0

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

^{n+m}1

^{n+m}0

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

Which of these languages are NOT context free?

.

Correct answer is :D

Solution :

A PDA can be built only for L1. It is not possible to build PDA for L2 and L3.

Question 11

.

Correct answer is :B

Solution :

Languages in option (A) And (D) are finite so both the options are eliminated. Only left options are (B) and (C). Both (B) and (C) look not regular as we don't have memory in DFA.

Question 12

.

Correct answer is :D

Solution :

It is regular L1=d(s) mod 5 =2 is regular with 5 states L2=d(s) mod 7 =4 is regular with 7 states therefore L1 ^ L2' should be regular because regular grammar are closed under intersection and compliment

Question 13

.

Correct answer is :A

Question 14

.

Correct answer is :B

Question 15

.

Correct answer is :D

Question 16

^{i}b

^{j}| i ≠ j}

.

Correct answer is :D