### SET 1

Question 1

**For any two languages L**_{1} and L_{2} such that L_{1} is context free and L_{2} is recursively enumerable but not recursive, which of the following is/are necessarily true?

I. L_{1}` (complement of L_{1}) is recursive II. L_{2} (complement of L_{2}) is recursive

III. L_{2}` is context-free

IV. L_{1}` ∪ L_{2}` is recursively enumerable

A : I only

B : III only

C : III and IV only

D : I and IV only

Answer Discuss it!

.

Correct answer is :D

Solution :

1 => This one is true, because L_{1} is context free which is nothing but recursive, recursive language is closed under complement hence true.

2 => If L_{2} and L_{2}` both are recursive enumerable then L_{2}` is recursive Hence option 2 is false

3 => is false because context free language does not closed under complement

4=> L_{1} ` = recursive and the union of context free and RE is RE(recursively enumerable).

Question 2

**Consider the DFAs M and N given below. The number of states in a minimal DFA that accepts the language L(M) ? L(N) is __________.**

Answer Discuss it!

.

Correct answer is :1

Solution :

M accepts the strings which end with a and N acceptsthe strings which end with B. Their intersection should accept empty language

Question 3

**Consider the NPDA < Q = {q0, q1, q2}, ∑ = {0, 1}, τ = {0, 1, ⊥ }, δ, q0, ⊥ , F = {q2} >, where (as per usual convention) Q is the set of states, ? is the input alphabet, ? is stack alphabet, ? is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?**

A : 10110

B : 10010

C : 01010

D : 01001

Answer Discuss it!

.

Correct answer is :D

Question 4

**Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?**

A : Q1 is in NP, Q2 in NP hard

B : Q2 is in NP, Q1 is NP hard

C : Both Q1 and Q2 are in NP

D : Both Q1 and Q2 are in NP hard

Answer Discuss it!

.

Correct answer is :A

Question 5

**Consider the following statements**

I. The complement of every Turing decidable language is Turing decidable

II. There exists some language which is in NP but is not turing decidable

III. If L is a language in NP, L is turing decidable

Which of the above statements is/are true?

A : Only II

B : Only III

C : Only I and II

D : Only I and III

Answer Discuss it!

.

Correct answer is :D

Solution :

Turing decidable => Recursive language

Turing recognizable => Recursive enumerable language

I) Complement of turning decidable language is decidable which is true.

III) True ( Theorem ) Which violates (II) hence key is D

Question 6

**Consider the alphabet Σ={0,1}, the null/empty string λand the sets of strings X**_{0},X,sub>1 and X_{2} generated by the corresponding non-terminals of regular grammar X_{0} , X _{1} and X_{2} are related as follows

X_{0} = 1 X_{1}

X_{1} = 0 X_{1} + 1 X_{2}

X_{2} = 0 X_{1} + {λ}

Which one of the following choices precisely represents the strings in X_{0}?

A : 10(0^{*} + (10)^{*})1

B : 10(0^{*} + (10)^{*})^{*}1

C : 1(0+10)^{*}1

D : 10(0+10^{*})^{*}1 + 110(0+10)^{*}1

Answer Discuss it!

.

Correct answer is :C

Question 7

**Which of the following languages is/are regular?**

L_{1} : { wxw^{R} | w,x ∈ {a,b} ^{*} nad |w| , |x| >0 } ,w^{R} is the reverse of sring w.

L_{2} : {a^{n}b^{m} | m ≠ n and m,n >=0 }

L_{3} : { a^{p}b^{q}c^{r} } p,q,r >=0}

A : L_{1} and L_{3} only

B : L_{1} only

C : L_{2} and L_{3} only

D : L_{3} only

Answer Discuss it!

.

Correct answer is :A

Solution :

L_{1} :w^{R} is reverse of string w ∴ Its is regular

L_{2} : m ≠ n ,that mean n is greater than m, or m is greater than n. So we need memory, so we can't draw DfA for it.

L_{3} It is regular (a+b+c)*

Question 8

**The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0+1)**^{*} (10 ) is _________________

Answer Discuss it!

.

Correct answer is :3

Solution :

(0+1)^{*} (10 )

Question 9

**Let L be the language represented by the regular expression Σ *0011 Σ * where Σ ={0,1}. What is the minimum number of states in a DFA that recognizes L (complement of L)?**

A : 4

B : 5

C : 6

D : 8

Answer Discuss it!

.

Correct answer is :B

Question 10

**Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?**

I. if L4 ∈ P, then L2 ∈

if L1 ∈ P or L3 ∈ P , then L2 ∈ P

III. L1∈ P,if and only if L3 ∈ P

if L4 ∈ P,then L1 ∈ P and L3 ∈ P

A : II only

B : III only

C : I and IV only

D : I only

Answer Discuss it!

.

Question 11

**Which of the following languages are context-free? **

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

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

L3 = { a^{m}b^{n} | m=2n+1 }

A : L1 and L2 only

B : L1 and L3 only

C : L2 and L3 only

D : L3 only

Answer Discuss it!

.

Correct answer is :C

Solution :

a^{m}b^{n}a^{n}b^{m} => This one is CFL

a^{m}b^{n}a^{m}b^{n} => by pumping lemma this one is not CFL.

{ a^{m}b^{n} | m=2n+1 } This is CFL.

Question 1

_{1}and L

_{2}such that L

_{1}is context free and L

_{2}is recursively enumerable but not recursive, which of the following is/are necessarily true?

I. L

_{1}` (complement of L

_{1}) is recursive II. L

_{2}(complement of L

_{2}) is recursive

III. L

_{2}` is context-free

IV. L

_{1}` ∪ L

_{2}` is recursively enumerable

.

Correct answer is :D

Solution :

1 => This one is true, because L

_{1}is context free which is nothing but recursive, recursive language is closed under complement hence true.

2 => If L

_{2}and L

_{2}` both are recursive enumerable then L

_{2}` is recursive Hence option 2 is false

3 => is false because context free language does not closed under complement

4=> L

_{1}` = recursive and the union of context free and RE is RE(recursively enumerable).

Question 2

.

Correct answer is :1

Solution :

M accepts the strings which end with a and N acceptsthe strings which end with B. Their intersection should accept empty language

Question 3

.

Correct answer is :D

Question 4

.

Correct answer is :A

Question 5

I. The complement of every Turing decidable language is Turing decidable

II. There exists some language which is in NP but is not turing decidable

III. If L is a language in NP, L is turing decidable

Which of the above statements is/are true?

.

Correct answer is :D

Solution :

Turing decidable => Recursive language

Turing recognizable => Recursive enumerable language

I) Complement of turning decidable language is decidable which is true.

III) True ( Theorem ) Which violates (II) hence key is D

Question 6

_{0},X,sub>1 and X

_{2}generated by the corresponding non-terminals of regular grammar X

_{0}, X

_{1}and X

_{2}are related as follows

X

_{0}= 1 X

_{1}

X

_{1}= 0 X

_{1}+ 1 X

_{2}

X

_{2}= 0 X

_{1}+ {λ}

Which one of the following choices precisely represents the strings in X

_{0}?

.

Correct answer is :C

Question 7

L

_{1}: { wxw

^{R}| w,x ∈ {a,b}

^{*}nad |w| , |x| >0 } ,w

^{R}is the reverse of sring w.

L

_{2}: {a

^{n}b

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

L

_{3}: { a

^{p}b

^{q}c

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

.

Correct answer is :A

Solution :

L

_{1}:w

^{R}is reverse of string w ∴ Its is regular

L

_{2}: m ≠ n ,that mean n is greater than m, or m is greater than n. So we need memory, so we can't draw DfA for it.

L

_{3}It is regular (a+b+c)*

Question 8

^{*}(10 ) is _________________

.

Correct answer is :3

Solution :

(0+1)

^{*}(10 )

Question 9

.

Correct answer is :B

Question 10

I. if L4 ∈ P, then L2 ∈

if L1 ∈ P or L3 ∈ P , then L2 ∈ P

III. L1∈ P,if and only if L3 ∈ P

if L4 ∈ P,then L1 ∈ P and L3 ∈ P

.

Question 11

L1 = { a

^{m}b

^{n}a

^{n}b

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

L2 = { a

^{m}b

^{n}a

^{m}b

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

L3 = { a

^{m}b

^{n}| m=2n+1 }

.

Correct answer is :C

Solution :

a

^{m}b

^{n}a

^{n}b

^{m}=> This one is CFL

a

^{m}b

^{n}a

^{m}b

^{n}=> by pumping lemma this one is not CFL.

{ a

^{m}b

^{n}| m=2n+1 } This is CFL.