Success TrackerSuccess Tracker
Log inSign up

GATE CS Theory of Computation Previous Year Questions

8 solved GATE CS questions on Theory of Computation, drawn from 1 exam year and grouped by year. Every question shows the official answer and a step-by-step solution.

GATE CS 20248 questions

  1. Set 1 Q23Let L1,L2L_1, L_2 be two regular languages and L3L_3 a language which is not regular. Which of the following statements is/are always TRUE?MSQ · +1 marks · Medium
  2. Set 1 Q50Consider the 5-state DFA MM accepting the language L(M)⊂(0+1)∗L(M) \subset (0 + 1)^* shown below. For any string w∈(0+1)∗w \in (0 + 1)^* let n0(w)n_0(w) be the number of 0's in…MSQ · +2 marks · Medium
  3. Set 1 Q59Let G=(V,Σ,S,P)G = (V, \Sigma, S, P) be a context-free grammar in Chomsky Normal Form with Σ={a,b,c}\Sigma = \{a, b, c\} and VV containing 10 variable symbols including the…NAT · +2 marks · Medium
  4. Set 1 Q61Consider the following two regular expressions over the alphabet {0,1}\{0,1\}: r=0∗+1∗r = 0^* + 1^* s=01∗+10∗s = 01^* + 10^* The total number of strings of length less…NAT · +2 marks · Medium
  5. Set 2 Q22Which one of the following regular expressions is equivalent to the language accepted by the DFA given below? [figure]MCQ · +1 marks · Medium
  6. Set 2 Q41Let MM be the 5-state NFA with ϵ\epsilon-transitions shown in the diagram below. [figure] Which one of the following regular expressions represents the…MCQ · +2 marks · Medium
  7. Set 2 Q52Consider a context-free grammar GG with the following 3 rules. S→aS,S→aSbS,S→cS \rightarrow aS, \quad S \rightarrow aSbS, \quad S \rightarrow c Let w∈L(G)w \in L(G). Let…MSQ · +2 marks · Medium
  8. Set 2 Q62Let L1L_1 be the language represented by the regular expression b∗ab∗(ab∗ab∗)∗b^*ab^*(ab^*ab^*)^* and L2={w∈(a+b)∗∣∣w∣≤4}L_2 = \{ w \in (a + b)^* \mid |w| \leq 4 \}, where ∣w∣|w| denotes…NAT · +2 marks · Medium

Other GATE CS topics

Engineering Mathematics(23)General Aptitude(20)Programming & Data Structures(17)Databases(12)Computer Networks(12)Computer Organization & Architecture(12)Operating System(10)Compiler Design(9)Digital Logic(8)Algorithms(5)

Practice Theory of Computation with adaptive difficulty

Timed practice, skill tracking, and AI explanations — free to start.

Start practicing free