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 274 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
- 274 attempts
- 0 upvotes
- 1 comment
Jun 9GATE & PSU CS