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 637 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: • 637 attempts Member since Sep 2020 GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com