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
- 2 upvotes
- 3 comments

Jun 9GATE & PSU CS

Posted by: