Time Left - 45:00 mins

GATE CS 2022 : Theory of Computation Quiz-10

Attempt now to get your rank among 410 students!

Question 1

How many unreachable states are in following DFA?

Question 2

If L1 is DCFL and L2 is CFL , then which statement is true ?

Question 3

Consider the following incomplete DFA

Find the missing transitions from states C&E in the above DFA to accept a language where each string starts and ends with same symbol and has length at least 2.

Question 4

Consider the following problems , which among them can be implemented on a Turing machine :

S1 : Calculating GCD of two numbers

S2 : Copying string

S3 : Predicting the result of tomorrow's cricket match

S4 : Calculating surface area of a given cone dimensions

Question 5

Set of all context free languages are?

Question 6

L1 is reducible to L2 and L2 is reducible to L3.  L3 is decidable. Which of the following can be valid using the above languages L1 and L2 ?

Question 7

which of the following grammar represent all the strings which can be generate by language L = {aibjck / i!=j and j!=k}

Question 8

Minimum number of states require to construct PDA acceptance by empty stack for the language L = {aibjckdl / i=k or j=l} is _____.

Question 9

Consider two languages L1 and L2 as :

L1 = {canbm |n,m 0 and n = m }

L2 = {danbm |n,m 0 and m = 2n }

What can you say about L1 U L2 ?

Question 10

Which of the following is True?

Question 11

Let L = {(aP)* | P is a prime number} and Σ={a}. The minimum number of states in NFA that accepts the language L are ________.

Question 12

The total number of substrings present in “GATE” is:

Question 13

Consider two languages, L1and L2:

L1= {an| n > = 0} and L2 = {bn | n > = 0}

Which of the following correctly represents L1 L2, where ‘ is the concatenation operation?

Question 14

Which of the following functions is total recursive function?

Question 15

Let R be a recursive language. Consider the following operations on languages.
I. Union
II. Intersection
III. Complement
Let X be the number of operations under which R is closed. Then the value of X is ________.
  • 410 attempts
  • 1 upvote
  • 1 comment