Time Left - 15:00 mins

GATE CS 2021 : Theory of computation (App update required to attempt this test)

Attempt now to get your rank among 651 students!

Question 1

Find the number of states in a minimal DFA for the State table given below?

Question 2

Which of the following statements are true?

i) Number of states in minimal DFA that accepts all the strings of a's and b's where nth symbol is fixed from right hand side is 2^n-1.

ii) Number Vertex cover problem is a example of NP complete problem.

iii) Inverse homomorphism of a language, h^-1(L) can't be {ε}.

iv) homomorphism of a language, h(L) can be {ε}.

v) h(h^-1(L)) ⊆ L.

vi) minimization of a total function leads to a total function.

vii) minimization of a total function leads to a partial function.

Question 3

Consider the DFA given below :

If final state is D , then language is

If final state is E , then language is

What is the relation between and .

Question 4

For language L , all strings start with ‘ a' only , ∑ (a,b)*
L₁= Language accepted by complement of NFA of L
L₂= Language accepted by complement of DFA of L

a) L₁ ≠ L'
b) L₂ = L'
c) L₁ = L'
d) L₁ = L₂
which one is true ?

Question 5

String accepted by following Epsilon NFA

Question 6

The minimal DFA of the following machine has:

651 attempts
3 upvotes
5 comments

Tags :

GATE & PSU CS Theory of Computation

Oct 1GATE & PSU CS