Time Left - 15:00 mins

# GATE CS 2022: Theory of computation-4 (App update required to attempt this test)

Attempt now to get your rank among 324 students!

Question 1

Finite automata requires minimum ______ number of stacks.

Question 2

What is the relation between DFA and NFA on the basis of computational power?

Question 3

Let L be a regular language. If minimal DFA corresponding to L and L′ contains 3 final states and 4 final states respectively, then the number of states in the minimal DFA corresponding to L is equal to ________.

Question 4Multiple Correct Options

L= { } which of the following is grammar of L.

Question 5

L and are 2 complementary languages , consider the following statements :

(RE : Recursively Enumerable)

(REC : Recursive)

S1 : Both are REC

S2 : Both are RE

S3 : One is REC , other is RE

S4 : Both are RE but not REC

S5 : One is REC and other is not RE

S6 : One is REC , other is RE but not REC.

S7 : One is not RE , other is RE.

How many of the above statements are false ____________.

Question 6

Number of productions will be after elimination of useless symbols and productions in given grammar

S ABC | BaB

A aA | BaC | aa

B aB | bb

C bAC

• 324 attempts