### SET 2

Question 1

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

A : The language L = { a^{n} b^{n} | n >= 0} is regular.

B : The language L = { a^{n} | n is prime } is regular.

C : The language L = { w | w has 3k +1b's for some k ∈ N with ∑ = {a,b} } is regular.

D : The language L ={ww | w ∈ ∑* with ∑ = {0,1} } is regular

Answer Discuss it!

.

Correct answer is :C

Solution :

(A) { a^{n} b^{n} | n >= 0} is a CFL but not regular, it requires memory for the representati

(B) L = { a^{n} | n is prime } is neither regular nor CFL

(C) L = { w | w has 3k +1b's for some k ∈ N with ∑ = {a,b} }

is a regular language, since the total count of b’s are multiple of 3 plus one. The regular expression is a * ba *(a *ba *ba * ba *)*+(a * ba * ba * ba *)*a * ba *

L ={ww | w ∈ ∑* with ∑ = {0,1} } is neither regular nor CFL

Question 2

**Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?**

A : { q_{0},q_{1},q_{2}}

B : { q_{0},q_{1}}

C : { q_{0},q_{1},q_{2},q_{3}}

D : { q_{3}}

Answer Discuss it!

.

Correct answer is :A

Solution :

d(q0 ,0011) = d(q0 ,011)

=d(q0,11)

=d({q0,q1},1)

=d(q0,1) U d(q1,1)

={q0,q1} U {q2}

{q0,q1,q2}

Question 3

**Let L be a language and L` be its complement. Which of the following is NOT a viable possibility?**

A : Neither L nor L` is recursively enumerable (r.e.).

B : One of L and L` is r.e. but not recursive; the other is not r.e.

C : Both L and L` are r.e. but not recursive.

D : Both L and L` are recursive.

Answer Discuss it!

.

Correct answer is :C

Solution :

Recursive languages are closed under complement.

If a language L is recursive enumerable but not recursive then its complement is not a recursive enumerable, so both L and L' are recursive enumerable but not recursive is not a viable possibility.

Question 4

**Which of the regular expressions given below represent the following DFA?**

I) 0*1(1+00*1)*

II) 0*1*1+11*0*1

III) (0+1)*1

A : I and II only

B : I and III only

C : II and III only

D : I, II and III

Answer Discuss it!

.

Correct answer is :B

Solution :

Given DFA will accept all the strings over e ={0,1} which are ending with 1.

0*1(1+ 00*1)* and(0 +1)*1, are the regular expressions for ending with 1.

Question 5

**Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?**

A : B :

C : D :

Answer Discuss it!

.

Correct answer is :D

Solution :

The most important open question in complexity theory is whether the P = NP , which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems ( since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.

Question 6

**If L1= { a**^{n} | n>=0 } and L2 = { b^{n} | n>=0 } , Consider

(I) L1.L2 is a regular language

(II) L1.L2 = { a^{n}b^{n} | n>0 }

Which one of the following is CORRECT ?

A : Only I

B : Only II

C : Both I and II

D : Neither I and II

Answer Discuss it!

.

Correct answer is :A

Solution :

L1.L2 is also regular since regular languages are closed under concatenation.

But L1.L2 is not { a^{n}b^{n} | n >=0 } because both the variable is independent in both languages.

Question 7

**Let m A <=**_{m} B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

A : If m A <=_{m} B and B is recursive then A is recursive.

B : If m A <=_{m} B and A is undecidable then B is undecidable.

C : If m A <=_{m} B and B is recursively enumerable then A is recursively enumerable.

D : If m A <=_{m} B and B is not recursively enumerable then A is not recursively enumerable.

Answer Discuss it!

.

Correct answer is :D

Question 8

**Let < M > be the encoding of a Turing machine as a string over S = {0,1} . Let L = {< M > |M is a Turning machine that accepts a string of length 2014}. Then, L is**

A : decidable and recursively enumerable

B : undecidable but recursively enumerable

C : undecidable and not recursively enumerable

D : decidable but not recursively enumerable

Answer Discuss it!

.

Correct answer is :B

Solution :

The language accepted by the Turing machine is recursively enumerable. If is undecidable as the Turing machine may halt or it may loop for the strings whose length is not equal to 2014.

Question 9

**Let L1 = w ∈ {0,1} * |w has at least as many occurrences of (110)’s as (011)’s}. Let L2 = {w Î 0,1 * | w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?**

A : L1 is regular but not L2

B : L2 is regular but not L1

C : Both L1 and L2 are regular

D : Neiher L1 and L2 are regular

Answer Discuss it!

.

Correct answer is :A

Solution :

The automaton for L1 is as follows and No finite state automata can be constructed for L2.

Question 10

**The length of the shortest string NOT in the language (over ∑ = {a,b}) of the following regular expression is _________. a*b* (ba)* a***

Answer Discuss it!

.

Correct answer is :3

Solution :

R.E= a * b*(ba)*a *

Length 0 is present as it accepts ∈ all length 1 strings are present (a,b)also aa,ab,ba,bb are present, But 'bab ' is not present. So it is 3

Question 11

**Let S be a finite non-empty alphabet and let * 2S be the power set of S * . Which one of the following is TRUE?**

A : Both 2S * and S * are countable

B : 2S * is countable S * is uncountable

C : 2S * is uncountable and S * is countable

D : Both 2S * and S * are uncountable

Answer Discuss it!

.

Correct answer is :C

Question 12

**Which one of the following problems is undecidable?**

A : Deciding if a given context-free grammar is ambiguous.

B : Deciding if a given string is generated by a given context-free grammar.

C : Deciding if the language generated by a given context-free grammar is empty.

D : Deciding if the language generated by a given context-free grammar is finite.

Answer Discuss it!

.

Correct answer is :A

Solution :

There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG, so it is undecidable.

Question 13

**Consider the following languages over the alphabet S = {0,1,c} **

L1={0^{n}1^{n} | n>=0 }

L2={ wcw^{r} | w ∈ {0,1} *}

L3={ww^{r} | w ∈ {0,1} *}

Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree languages?

A : None of the languages

B : Only L1

C : Only L1 and L2

D : All the three languages

Answer Discuss it!

.

Correct answer is :C

Solution :

For the languages L1 and L2 we can have deterministic push down automata, so they are DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3 is not a deterministic CFL.

Question 14

**Consider the decision problem 2CNFSAT defined as follows: **

{ ∅ | ∅ is a satisfiable propositional formula in CNF with at most two literal per clause}

For example, ∅ = (x1 ∨ &x2) ∧ (x1 ∨ x3`) ∧ (x2 ∨ x4) is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

A : NP-Complete.

B : solvable in polynomial time by reduction to directed graph reachability.

C : solvable in constant time since any input instance is satisfiable.

D : NP-hard, but not NP-complete.

Answer Discuss it!

.

Correct answer is :B

Question 1

.

Correct answer is :C

Solution :

(A) { a

^{n}b

^{n}| n >= 0} is a CFL but not regular, it requires memory for the representati

(B) L = { a

^{n}| n is prime } is neither regular nor CFL

(C) L = { w | w has 3k +1b's for some k ∈ N with ∑ = {a,b} }

is a regular language, since the total count of b’s are multiple of 3 plus one. The regular expression is a * ba *(a *ba *ba * ba *)*+(a * ba * ba * ba *)*a * ba *

L ={ww | w ∈ ∑* with ∑ = {0,1} } is neither regular nor CFL

Question 2

.

Correct answer is :A

Solution :

d(q0 ,0011) = d(q0 ,011)

=d(q0,11)

=d({q0,q1},1)

=d(q0,1) U d(q1,1)

={q0,q1} U {q2}

{q0,q1,q2}

Question 3

.

Correct answer is :C

Solution :

Recursive languages are closed under complement.

If a language L is recursive enumerable but not recursive then its complement is not a recursive enumerable, so both L and L' are recursive enumerable but not recursive is not a viable possibility.

Question 4

I) 0*1(1+00*1)*

II) 0*1*1+11*0*1

III) (0+1)*1

.

Correct answer is :B

Solution :

Given DFA will accept all the strings over e ={0,1} which are ending with 1.

0*1(1+ 00*1)* and(0 +1)*1, are the regular expressions for ending with 1.

Question 5

.

Correct answer is :D

Solution :

The most important open question in complexity theory is whether the P = NP , which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems ( since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.

Question 6

^{n}| n>=0 } and L2 = { b

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

(I) L1.L2 is a regular language

(II) L1.L2 = { a

^{n}b

^{n}| n>0 }

Which one of the following is CORRECT ?

.

Correct answer is :A

Solution :

L1.L2 is also regular since regular languages are closed under concatenation.

But L1.L2 is not { a

^{n}b

^{n}| n >=0 } because both the variable is independent in both languages.

Question 7

_{m}B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

.

Correct answer is :D

Question 8

.

Correct answer is :B

Solution :

The language accepted by the Turing machine is recursively enumerable. If is undecidable as the Turing machine may halt or it may loop for the strings whose length is not equal to 2014.

Question 9

.

Correct answer is :A

Solution :

The automaton for L1 is as follows and No finite state automata can be constructed for L2.

Question 10

.

Correct answer is :3

Solution :

R.E= a * b*(ba)*a *

Length 0 is present as it accepts ∈ all length 1 strings are present (a,b)also aa,ab,ba,bb are present, But 'bab ' is not present. So it is 3

Question 11

.

Correct answer is :C

Question 12

.

Correct answer is :A

Solution :

There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG, so it is undecidable.

Question 13

L1={0

^{n}1

^{n}| n>=0 }

L2={ wcw

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

L3={ww

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

Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree languages?

.

Correct answer is :C

Solution :

For the languages L1 and L2 we can have deterministic push down automata, so they are DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3 is not a deterministic CFL.

Question 14

{ ∅ | ∅ is a satisfiable propositional formula in CNF with at most two literal per clause}

For example, ∅ = (x1 ∨ &x2) ∧ (x1 ∨ x3`) ∧ (x2 ∨ x4) is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

.

Correct answer is :B