### SET 3

Question 1

**Which of the following pairs have DIFFERENT expressive power?**

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 : Deterministic single-tape Turing machine and Non-deterministic single tape Turing machine

D : Single-tape Turing machine and multi-tape Turing machine

Answer Discuss it!

.

Correct answer is :B

Solution :

NPDA is more powerful than DPDA. Hence answer is (B)

Question 2

**Definition of a language L with alphabet {a} is given as following**

L = { a^{nk} | k > 0, and n is a positive integer constant }

What is the minimum number of states needed in a DFA to recognize L?

A : k+1

B : n+1

C : 2^{n+1}

D : 2^{k+1}

Answer Discuss it!

.

Correct answer is :B

Solution :

(n + 1) states as n is constant and k can have any value so if n = 2 then we can do this with k=1 and with 3 states.

Question 3

**A deterministic finite automation (DFA)D with alphabet ? = {a,b} is given below Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?**

A : B :

C : D :

Answer Discuss it!

.

Correct answer is :A

Solution :

Options B and C will accept the string b

Option – D will accept the string “bba”

Both are invalid strings.

So the minimized DFA is option A

Question 4

**Let P be a regular language and Q be a context free language such that Q ⊆ P.(For example, let P be the language represented by the regular expression p*q* and Q be {p**^{n}q^{n} | n ∈ N} ). Then which of the following is ALWAYS regular?

A : p ∩ Q

B : P-Q

C : ∑ ^{*} - P

D : ∑ ^{*} - Q

Answer Discuss it!

.

Correct answer is :C

Solution :

∑ ^{*} - P is the complement of P so it is always regular, since regular languages are closed under complementation

Question 5

**Consider the language L1,L2,L3 as given below.**

L1={ 0^{p} 1^{q} | p,q ∈ N }

L2={ 0^{p} 1^{q} | p,q ∈ N and p=q }

L3={ 0^{p} 1^{q} 0^{r} | p,q,r ∈ N and p=q=r }

Which of the following statements is NOT TRUE?

A : Push Down Automata (PDA) can be used to recognize L1 and L2

B : L1 is a regular language

C : All the three languages are context free

D : Turing machine can be used to recognize all the three languages

Answer Discuss it!

.

Correct answer is :C

Solution :

L1: regular language

L2: context free language

L3: context sensitive language

Question 6

**Which of the following problems are decidable?**

1)Does a given program ever produce an output?

2)If L is context-free language, then, is L` also context-free?

3)If L is regular language, then, is L` also regular

4)If L is recursive language, then, is L` also recursive?

A : 1,2,3,4

B : 1,2

C : 2,3,4

D : 3,4

Answer Discuss it!

.

Correct answer is :D

Solution :

CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

Question 7

**Given the language L-{ab, aa, baa}, which of the following strings are in L*?**

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

A : 1,2 and 3

B : 2,3 and 4

C : 1,2 and 4

D : 1,3 and 4

Answer Discuss it!

.

Correct answer is :C

Solution :

L ={ab, aa, baa}

Let S1 = ab , S2 = aa and S3 =baa

abaabaaabaa can be written as S1S2S3S1S2 aaaabaaaa can be written as S1S1S3S1 baaaaabaa can be written as S3S2S1S2

Question 8

**What is the complement of the language accepted by the NFA shown below?**

A : ∅

B : { ∈ }

C : a^{*}

D : { a , ∈ }

Answer Discuss it!

.

Correct answer is :B

Solution :

Language accepted by NFA is a+, so complement of this language is {∈}

Question 9

**Assuming P ≠ NP, which of the following is TRUE?**

A : NP-complete = NP

B : NP-complete ∩ P = ∅

C : NP-hard = NP

D : P = NP-complete

Answer Discuss it!

.

Correct answer is :B

Solution :

If P!=NP, then it implies that no NP-Complete problem can be solved in polynomialtime which implies that the set P and the set NPC are disjoint.

Question 10

**Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.**

A : B :

C : D :

Answer Discuss it!

.

Correct answer is :D

Question 11

**Which of the following statements are TRUE?**

(1) The problem of determining whether there exists a cycle in an undirected graph is in P.

(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.

(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

A : 1,2 and 3

B : 1 and 2 only

C : 2 and 3 only

D : 1 and 3 only

Answer Discuss it!

.

Correct answer is :A

Solution :

1. Cycle detection using DFS: O(V+ E) = O(V^{2} ) and it is polynomial problem

2.Every P-problem is NP(since P ⊂ NP)

3.NP - complete ∈ NP

Hence, NP-complete can be solved in non-deterministic polynomial time

Question 12

**Which of the following statements is/are FALSE?**

(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

(2) Turing recognizable languages are closed under union and complementation.

(3) Turing decidable languages are closed under intersection and complementation

(4) Turing recognizable languages are closed under union and intersection.

A : 1 and 4 only

B : 1 and 3 only

C : 2 only

D : 3 only

Answer Discuss it!

.

Correct answer is :C

Solution :

(1) NTM ≅ DTM

(2) RELs are closed under union & but not complementation

(3) Turing decidable languages are recursive and recursive languages are closed under intersection and complementation

(4) RELs are closed under union & intersection but not under complementation

Question 13

**Consider the languages L1 =∅ and L2 ={ a} . Which one of the following represents L1 L2* U L1* ?**

A : {∈}

B : ∅

C : a*

D : {∈ , a}

Answer Discuss it!

.

Correct answer is :A

Solution :

Concatenation of empty language with any language will give the empty language and L1* = ∅* = ∈ . Hence L1L2* U L1* = {∈}

Question 14

**Which of the following is/are undecidable? **

1. G is a CFG. Is L(G) =∅?

2. G is a CFG. IS L(G) = ∑*?

3. M is a Turning machine. Is L(M) regular?

4. A is a DFA and N is a NFA. Is L(A) = L(N)?

A : 3 only

B : 3 and 4 only

C : 1,2 and 3 only

D : 2 and 3 only

Answer Discuss it!

.

Correct answer is :D

Solution :

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable

Question 15

**Consider the DFA given below.**

Which of the following are FALSE?

1. Complement of L(A) is context–free

2. L(A) = L((11* 0 + 0)(0 +1)* 0 *1*)

3. For the language accepted by A, A is the minimal DFA

4. A accepts all strings over {0, 1} of length at least 2

A : 1 and 3 only

B : 2 and 4 only

C : 2 and 3 only

D : 3 and 4 only

Answer Discuss it!

.

Correct answer is :D

Solution :

(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.

(2) L(A) =(11*0 + 0)(0 +1)* 0*1* = 1*0 (0 +1)* Language has all strings where each string contains ‘0’.

(3) A is not minimal, it can be constructed with 2 states

(4) Language has all strings, where each string contains ‘0’. (atleast length one)

Question 16

**Consider the following languages**

L1={0^{p}1^{q}0^{r} | p,q,r >=0 }

L2={0^{p}1^{q}0^{r} | p,q,r >=0 ,p≠r }

Which one of the following statements is FALSE?

A : L2 is context free

B : L1 ∩ L2 is context free

C : Complement of L1 is recursive

D : Complement of L1 is context free but not regular

Answer Discuss it!

.

Correct answer is :D

Question 1

.

Correct answer is :B

Solution :

NPDA is more powerful than DPDA. Hence answer is (B)

Question 2

L = { a

^{nk}| k > 0, and n is a positive integer constant }

What is the minimum number of states needed in a DFA to recognize L?

.

Correct answer is :B

Solution :

(n + 1) states as n is constant and k can have any value so if n = 2 then we can do this with k=1 and with 3 states.

Question 3

.

Correct answer is :A

Solution :

Options B and C will accept the string b

Option – D will accept the string “bba”

Both are invalid strings.

So the minimized DFA is option A

Question 4

^{n}q

^{n}| n ∈ N} ). Then which of the following is ALWAYS regular?

.

Correct answer is :C

Solution :

∑

^{*}- P is the complement of P so it is always regular, since regular languages are closed under complementation

Question 5

L1={ 0

^{p}1

^{q}| p,q ∈ N }

L2={ 0

^{p}1

^{q}| p,q ∈ N and p=q }

L3={ 0

^{p}1

^{q}0

^{r}| p,q,r ∈ N and p=q=r }

Which of the following statements is NOT TRUE?

.

Correct answer is :C

Solution :

L1: regular language

L2: context free language

L3: context sensitive language

Question 6

1)Does a given program ever produce an output?

2)If L is context-free language, then, is L` also context-free?

3)If L is regular language, then, is L` also regular

4)If L is recursive language, then, is L` also recursive?

.

Correct answer is :D

Solution :

CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

Question 7

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

.

Correct answer is :C

Solution :

L ={ab, aa, baa}

Let S1 = ab , S2 = aa and S3 =baa

abaabaaabaa can be written as S1S2S3S1S2 aaaabaaaa can be written as S1S1S3S1 baaaaabaa can be written as S3S2S1S2

Question 8

.

Correct answer is :B

Solution :

Language accepted by NFA is a+, so complement of this language is {∈}

Question 9

.

Correct answer is :B

Solution :

If P!=NP, then it implies that no NP-Complete problem can be solved in polynomialtime which implies that the set P and the set NPC are disjoint.

Question 10

.

Correct answer is :D

Question 11

(1) The problem of determining whether there exists a cycle in an undirected graph is in P.

(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.

(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

.

Correct answer is :A

Solution :

1. Cycle detection using DFS: O(V+ E) = O(V

^{2}) and it is polynomial problem

2.Every P-problem is NP(since P ⊂ NP)

3.NP - complete ∈ NP

Hence, NP-complete can be solved in non-deterministic polynomial time

Question 12

(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

(2) Turing recognizable languages are closed under union and complementation.

(3) Turing decidable languages are closed under intersection and complementation

(4) Turing recognizable languages are closed under union and intersection.

.

Correct answer is :C

Solution :

(1) NTM ≅ DTM

(2) RELs are closed under union & but not complementation

(3) Turing decidable languages are recursive and recursive languages are closed under intersection and complementation

(4) RELs are closed under union & intersection but not under complementation

Question 13

.

Correct answer is :A

Solution :

Concatenation of empty language with any language will give the empty language and L1* = ∅* = ∈ . Hence L1L2* U L1* = {∈}

Question 14

1. G is a CFG. Is L(G) =∅?

2. G is a CFG. IS L(G) = ∑*?

3. M is a Turning machine. Is L(M) regular?

4. A is a DFA and N is a NFA. Is L(A) = L(N)?

.

Correct answer is :D

Solution :

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable

Question 15

Which of the following are FALSE?

1. Complement of L(A) is context–free

2. L(A) = L((11* 0 + 0)(0 +1)* 0 *1*)

3. For the language accepted by A, A is the minimal DFA

4. A accepts all strings over {0, 1} of length at least 2

.

Correct answer is :D

Solution :

(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.

(2) L(A) =(11*0 + 0)(0 +1)* 0*1* = 1*0 (0 +1)* Language has all strings where each string contains ‘0’.

(3) A is not minimal, it can be constructed with 2 states

(4) Language has all strings, where each string contains ‘0’. (atleast length one)

Question 16

L1={0

^{p}1

^{q}0

^{r}| p,q,r >=0 }

L2={0

^{p}1

^{q}0

^{r}| p,q,r >=0 ,p≠r }

Which one of the following statements is FALSE?

.

Correct answer is :D