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 653 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 2n-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)*
L1= Language accepted by complement of NFA of L
L2= Language accepted by complement of DFA of L

a) L1 ≠ L'
b) L2 = L'
c) L1 = L'
d) L1 = L2

which one is true ?

Question 5

String accepted  by  following Epsilon NFA

Question 6

The minimal DFA of the following  machine has:
• 653 attempts