TOC Gate Questions

Here, We will see (Theory of Computation) TOC GATE Questions from previous year’s papers and the syllabus of Theory of Computation for the GATE Exam.

1. Theory of Computation in Gate CSE Exam

The Theory of Computation (TOC) is a foundational subject in computer science, forming a critical part of the GATE CSE syllabus. It explores the mathematical underpinnings of computation, focusing on what problems can be solved algorithmically and the inherent limitations of computational models. For GATE aspirants, mastering TOC is essential due to its recurring weightage (6–9% in recent years) and its role in testing analytical and problem-solving skills.

2. Theory of Computation Syllabus

The syllabus for Theory of Computation in GATE CSE includes:

1. Regular Languages and Finite Automata: Topics include regular expressions, deterministic/non-deterministic finite automata (DFA/NFA), and equivalence between them.
2. Context-Free Languages and Pushdown Automata: Context-free grammars (CFGs), parsing, and the relationship between CFGs and pushdown automata (PDA).
3. Turing Machines and Computability: Understanding Turing machines as universal computational models and exploring decidability, reducibility, and the Halting Problem.
4. Undecidability and Complexity: The Pumping Lemma for proving language non-regularity/non-context-freeness and an introduction to complexity classes like P, NP, and NP-completeness.

(Theory of Computation) TOC GATE Questions

Q. The CFG S → aS |bS |a |b is equivalent to

1. (a+b)
2. (a+b)(a+b)*
3. (a+b)(a+b)
4. all of these

Q. Let G be a grammar in CFG and let W₁,W₂ Є L(G) |W₁|=|W₂| such that then which of the following statements is true?

1. Any derivation of W₁ has exactly the same number of steps as any derivation of W₂.
2. Different derivation have different length.
3. Some derivation of W₁ may be shorter than the derivation of W₂.
4. None of the options

Q. If L₁ is CFL and L₂ is regular language which of the following is false?

1. L₁-L₂ is not Context free
2. L₁ intersection L₂ is Context free
3. ~L₁ is Context free
4. Both 1 and 3

Q. _________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms.

1. NP
2. P
3. Hard
4. Complete

Q. If L₁ and L₂ are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

1. L₁L₂
2. L₁∩L₂
3. L₁∩R
4. L₁∪L₂

Q. Which of the following definitions generates the same languages as L, where
L={xⁿyⁿ,n≥1}
i. E → xEy | xy
ii. xy | x⁺ xyy⁺
iii. x⁺ y⁺

1. i only
2. i and ii only
3. ii and iii only
4. ii only

Q. Let n is the length of string to test for membership, then the number of table entry in CYK algorithm is

1. n(n+1)
2. n²+1
3. n²-1
4. n(n+1)/2

Q. The following grammer is an example of ________ .
A→aABC
CB→Bc
A→abc
bB→bb
B→cba

1. Type 0 Grammer
2. Type 1 Grammer
3. Type 2 Grammer
4. Type 3 Grammer

Q. Consider the finite automata given below
The language b accepted by this automata is a given by the regular expression :

1. b*ab*ab*ab
2. (a+b)*
3. b*a(a+b)*
4. b*ab*ab*

Q. Given a graph with n vertices, deciding if there exists a clique of size≥195 is :

1. Solvable in polynomial time
2. NP
3. NP-Complete
4. None of the above

Q. A language L is recognizable by a turing machine M if and only if L is a ________ language.

1. Type 0
2. Type 1
3. Type 2
4. Type 3

Q. Bounded minimalization is a technique for

1. proving whether a promotive recursive function is turning computable or not
2. proving whether a primitive recursive function is a total function or not
3. generating primitive recursive functions
4. generating partial recursive functions

Q. Which of the following are undecidable?
P1 : The language generated by some CFG contains any words of length less than some given number n.
P2 : Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements
P3 : Any given CFG is ambiguous or not.
P4 : For any given CFG G, to determine whether epsilon belongs to L(G)

1. P2 only
2. P1 and P2 only
3. P2 and P3 only
4. P3 only

Q. Consider the grammar with non terminals N={S,C,S₁} terminals T = {a,b,i,t,e} with S as the start symbol, and the following set of rules :
S → iC_tSS₁|a
S₁ → eS|Є
C → b
The grammar is not LL(1) because:

1. It is left recursive
2. It is right recursive
3. It is ambiguous
4. It is not context free

Q. If T1 and T2 are two Turing machines. The composite can be represented using the expression :

1. T1T2
2. T1ՍT2
3. T1×T2
4. None of the options

Q. Which of the following statements is true ?

1. Melay and Moore machines are language acceptors.
2. Finite State automata is language translator.
3. NPDA is more powerful than DPDA.
4. Melay machine is more powerful than Moore machine.

Q. Palindromes can’t be recognized by any Finite State Automata because:

1. FSA cannot remember arbitrarily large amount of information.
2. FSA cannot deterministically fix the midpoint.
3. Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half.
4. All of the above.

Q. Given two DFA’s M₁ and M₂. They are equivalent if

1. M₁ and M₂ has the same number of states
2. M₁ and M₂accepts the same language i.e L(M₁)=L(M₂)
3. M₁ and M₂ has the same number of final states
4. None of the above

Q. (00+01+10)(0+1)* represents

1. Strings not starting with 11
2. Strings of odd length
3. Strings starting with 00
4. Strings of even length

Q. Let L = L₁∩L₂, where L₁ and L₂ are language defined below :
L₁ = {a^mb^maⁿbⁿ m,n>0}
L₂ = {aⁱb^jc^k i,j,k>0}
Then L is

1. Not Recursive
2. Regular
3. Context free but not regular
4. Recursively enumerable but not context free

Q. Two finite state machines are said to be equivalent if they

1. have same number of states
2. have same number of edges
3. have same number of states and edges
4. recognize same set of tokens

Q. The automatIon which allows transformation to a new state without consuming any input symbols

1. NFA
2. DFA
3. NFA-1
4. All of the options

Q. _______ is the most general phase structured grammar.

1. Regular
2. Context free
3. Context sensitive
4. All of the above

Q. Complement of a DFA can be obtained by :

1. making starting state as final state.
2. make final as a starting state.
3. making final states non-final and non-final as final.
4. None of the option

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

1. DFA>NFA
2. NFA>DFA
3. Equal
4. Can’t be said

Q. Concatenation Operation refers to which of the following set operations :

1. Union
2. Dot
3. Kleene
4. None of the options

Q. Finite automata requires minimum ________ number of stacks.

1. 1
2. 0
3. 2
4. None of the options

Q. Assume that P and NP are different i.e. P!=NP then for the expression NP-Complete∩P=?. Which among the following is correct ?

1. NP-Hard
2. 🚫
3. P
4. NP-Complete

Q. What is the complement of the language accepted by the NFA shown below?
1.O
2. {Є}
3. a*
4. {a,Є}

1. 1
2. 2
3. 3
4. 4

Q. Consider the following Finite State Automaton. The language accepted by the automaton is given by the regular expression.

1. ab*b*
2. a*b*
3. b*b
4. b*ab*

Q. Regarding power of recognition of language, which of the following statements is false?

1. Non deterministic finite-state automata are equivalent to deterministic finite-state automata.
2. Non-deterministic push-down automata are equivalent to deterministic push-down automata.
3. Non-deterministic Turing Machines are equivalent to deterministic push-down automata.
4. Multi-tape Turing Machines are equivalent to Single-tape Turing Machines.

Q. Consider the following problem X. Given a Turing machine M over the input alphabet ∑, any state q of M and a word ꙍ Є ∑*, does the computation of M on ꙍ visit the state of q?
Which of the following statements about X is correct?

1. X is decidable
2. X is undecidable but partially decidable
3. X is undecidable and not even partially decidable
4. X is not a decision problem

Q. If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called

1. decidable
2. undecidable
3. interpretive
4. non-deterministic

Q. The defining language for developing a formalism in which language definitions can be stated, is called

1. syntactic meta language
2. decidable language
3. intermediate language
4. high level language

Q. A finite automaton accepts which type of language :

1. Type 0
2. Type 1
3. Type 2
4. Type 3

Q. Which of the following statement is true?

1. Deterministic context free language are closed under complement.
2. Deterministic context free language are not closed under Union.
3. Deterministic context free language are closed under intersection with the regular set.
4. All of the options

Q. Which of the following is a correct hierarchical relationships of the following where
L₁ : set of languages accepted by NFA
L₂ : set of languages accepted by DFA
L₃ : set of languages accepted by DPDA
L₄ : set of languages accepted by NPDA
L₅ : set of recursive language
L₆ : set of recursive enumerable languages?

1. L₁,L₂⊂L₃⊂L₄⊂L₅⊂L₆
2. L₁⊂L₂⊂L₃⊂L₄⊂L₅⊂L₆
3. L₂⊂L₁⊂L₃⊂L₄⊂L₅⊂L₆
4. L₁⊂L₂⊂L₃⊂L₄⊂L₆⊂L₅

Q. How many DFA’s exits with two states over input alphabet {0,1}

1. 16
2. 26
3. 32
4. 64

Q. Which of the following statements about the parser is/are correct?
I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than canonical LR.

1. I only
2. II only
3. III only
4. II and III only

Q. If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is in

1. P
2. NP
3. both (1) and (2)
4. None of these

Q. Which of the following problem is not NP complete but undecidable?

1. Partition Problem
2. Halting Problem
3. Hamiltonian Circuit
4. Bin Packing

Q. The logic of pumping lemma is a good example of

1. the pigeon-hole principle
2. the divide and conquer technique
3. recursion
4. iteration

Q. Cardinality of relationship advisor to each entity sets instructor and student will be:

1. One to many
2. One to one
3. Many to many
4. Many to one

Q. Which machine is equally powerful in both deterministic and non-deterministic form?

1. Push Down Automata
2. Turing machine
3. Linear Bounded Automata
4. None of the options

Q. Choose the correct statements.

1. A total recursive function is also a partial recursive function
2. A partial recursive function is also a total recursive function
3. A partial recursive function is also a primitive recursive function
4. None of the above

Q. Recursive enumerable languages are not closed under ___________ .

1. Set difference
2. Complement
3. Both (A) and (B)
4. None of the options

Q. If any string of a language L can be effectively enumerated by an enumerator in a lexicographic order then language L is _________ .

1. Regular
2. Context free but not necessarily regular
3. Recursive but not necessarily context free
4. Recursively enumerable but not necessarily recursive

Q. The collection of Turing recognizable languages are closed under:
i. Union
ii. Intersection
iii. Complement
iv. Concatenation
v. Star Closure

1. (i) Only
2. Both (i),(iv)
3. (i),(ii),(iv)and(v)
4. All of the options

Q. Which of the following machine model can be used in a necessary and sufficient sense for lexical analysis in modern computer language?

1. Deterministic Push down Automata
2. Finite Automata
3. Non-Deterministic Finite Automata
4. Turing Machine

Q. Let L be a language and L’ be its complement. Which one of the following is NOT a viable possibility?

1. Neither L nor L’ is RE.
2. One of the L and L’ is RE but not recursive;the other is not RE.
3. Both L and L’ are RE but not recursive.
4. Both L and L’ are recursive.

Q. Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not recursive language. Which one of the following is TRUE?

1. L₁‘ is recursive and L₂‘ is recursively enumerable.
2. L₁‘ is recursive and L₂‘ is not recursively enumerable.
3. L₁‘ and L₂‘ is recursively enumerable.
4. L₁‘ is recursively enumerable and L₂‘ is recursive.

Q. A language L for which there exists a TM ‘T’, that accepts every word in L and either rejects or loops for every word that is not in L, is said to be

1. Recursive
2. Recursively enumerable
3. NP-HARD
4. None of the above

Q. Identify the true statement from the given statements:
1. A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
2. The complement of a recursive languages is recursive
3. The complement of a context-free language is context-free

1. Only 1
2. 1 and 2
3. 1, 2 and 3
4. 2 and 3

Q. Consider the following types of languages:
L1 : Regular,
L2 : Context-free,
L3 : Recursive,
L4 : Recursively enumerable.
Which of the following is/are TRUE?
I. L3’ՍL4is recursively enumerable
II. L2ՍL3 is recursive
III. L1*ՍL2is context-free
IV. L1ՍL2’is context-free

1. I only
2. I and III only
3. I and IV only
4. I,II and III only

Q. Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a,b}?

1. a*b*
2. (a|b)*
3. (ab)⁺
4. (a|b*)

Q. Regular expression (a|b)(a|b) denotes the set

1. {a,b,ab,aa}
2. {a,b,ba,bb}
3. {a,b}
4. {aa,ab,ba,bb}

Q. Let P,Q,R be a regular expression over ∑. If does not contain null string, then R=Q+RP has a unique solution __________ .

1. Q*P
2. QP*
3. Q*P*
4. (P*Q*)*

Q. (0+ε)(1+ε) represents :

1. {0,1,01,ε}
2. {0,1,ε}
3. {0,1,01,11,00,10,ε}
4. {0,1}

Q. Complement of (a+b)* will be :

1. Phi(Φ)
2. Null
3. a
4. b

Q. A regular expression is (a+b*c) is equivalent to

1. set of strings with either a or one or more occurrence of b followed by c.
2. (b*c+a)
3. set of strings with either a or zero or more occurrence of b followed by c.
4. Both (B) and (C)

Q. According to the given language, which among the following expressions does it correspond to ?
Language L = {xЄ{0,1} | x is of length 4 or less}

1. (0+1+0+1+0+1+0+1)⁴
2. (0+1)⁴
3. (01)⁴
4. (0+1+ε)⁴

Q. What is the meaning of regular expression ∑*001∑*?

1. Any string containing ‘1’ as substring
2. Any string containing ‘01’ as substring
3. Any string containing ‘011’ as substring
4. All string containing ‘001’ as substring

Q. Which of the following regular expression is equal to (r₁+r₂)*?

1. r₁*r₂*
2. (r₁r₂)*
3. r₁*r₂*+r₁r₂
4. (r₁*r₂*)*

Q. Which of the following is equivalent regular expressions?
i. ((01)*(10)*)*
ii. (10+01)*
iii. (01)*+(11)*
iv. (0*+(11)*+0*)*)

1. (i) and (ii)
2. (ii) and (iii)
3. (iii) and (iv)
4. (iv) and (i)

Q. The string 1101 does not belong to the set represented by

1. (00+(11)*0)
2. 1(0+1)*101
3. (10)*(01)*(00+11)*
4. 110*(0+1)

Q. Which of the following languages over the alphabet [01] is described by the given regular expression: (0+1)*(0+1)*1?

1. The set of all strings containing the substring 11
2. The set of all strings containing at most two 1’s
3. The set of all strings containing at least two 1’s
4. The set of all strings that begins and ends with only 0

Q. If L be a language recognizable by a finite automaton, then language from {L}={ω such that ω is a prefix of υ where υЄL}, is

1. regular language.
2. context-free language.
3. context-sensitive language.
4. recursive enumeration language

Q. Which of the following statements is correct?

1. A={aⁿbⁿ | n=0,1,2,3….} is regular language
2. Set B of all strings of equal number of a’s and b’s defines a regular language
3. L(A*B*)∩B gives the set A
4. None of these.

Q. If L1 and L2 are regular sets then intersection of these two will be :

1. Regular
2. Non Regular
3. Recursive
4. Non Recursive

Q. In the Given language L={ab,aa,baaa}, __ number of strings are in L*
1. baaaba
2. aabaaaa
3. baaabaaaabaa
4. baaabaaa

1. 1
2. 2
3. 3
4. 4

Q. Which of the following is wrong?

1. Turing machine is a simple mathematical model of general purpose computer
2. Turing machine is more powerful than finite automata
3. Turing Machine can be simulated by a general purpose computer
4. All of these

Q. Which of the following statement is true?
S₁ : The power of a multi-tape Turing machine is greater than the power of a single tape Turing machine.
S₂ : Every non-deterministic Turing machine has an equivalent deterministic Turing machine.

1. S₁
2. S₂
3. Both S₁ and S₂
4. None of the options