GATE CS 2022 : Theory of Computation Quiz-10

How many unreachable states are in following DFA?

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

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.

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

Set of all context free languages are?

which of the following grammar represent all the strings which can be generate by language L = {aⁱb^jc^k / i!=j and j!=k}

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

Consider two languages L1 and L2 as :

L1 = {caⁿb^m |n,m ≥ 0 and n = m }

L2 = {daⁿb^m |n,m ≥ 0 and m = 2n }

What can you say about L1 U L2 ?

Which of the following is True?

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

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

Consider two languages, L₁and L₂:

L₁= {aⁿ| n > = 0} and L₂ = {bⁿ | n > = 0}

Which of the following correctly represents L₁⋅ L₂, where ‘⋅’ is the concatenation operation?

Which of the following functions is total recursive function?

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 ________.