[GATE CS 2011] Definition of a language L with alphabet {a} is given as following. L= \{a^{nk} | \text{k>0, and n is a positive integer constant}\} What is the minimum number of states needed in DFA to recognize L?

A.k+1

B.n+1

C.n+k

D.L cannot be generated by DFA

Correct Answer: n+1

Question 2

Calculate the roots of the following degree 2 univariate polynomial. x^2+3x-4=0

A.x=4 and x=1

B.x=4 and x=-1

C.x=-4 and x=1

D.x=-4 and x=-1

Correct Answer: x=-4 and x=1

Question 3

Let a \neq 0 be an element of a commutative ring such that a^2b=0. Which of the following is true?

A.a is an identity element of the ring

B.a is a zero divisor of the ring

C.b is inverse of a

D.All of the above

Correct Answer: a is a zero divisor of the ring

Question 4

Which of the following options are true for the language L = \{a^n | \text{n is a perfect square} \}

A.L is regular

B.L is context-free but not regular

C.L is neither regular nor context-free but accepted by a Turing machine

D.None of the above

Correct Answer: L is neither regular nor context-free but accepted by a Turing machine

Question 5

Consider the following recurrence T(n) = 4T(n/3) + n Which one of the following options is true?

Correct Answer: Question visual

Week 0 of 13

This is the first assignment

Week 1 · Quiz: Week 1 : Assignment 1