Skip to content
GATETECH

GATE CS Theory of Computation questions

Practise Theory of Computation questions for GATE CS. Explore official PYQs and original subject-wise quizzes, check answers and view available solutions. Free, no sign-in.

Subject, topic, year and type filter the full library. Match any choice within a filter, and all selected filter categories. Search, source and sort apply to this page.

20 on this page
Official PYQ2012Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Assuming P≠NP\textsf{P} \neq \textsf{NP}, which of the following is TRUE?
Official PYQ2011Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Let PP be a regular language and QQ be a context-free language such that Q⊆PQ \subseteq P. (For example, let PP be the language represented by the regular expression p∗q∗p^*q^* and QQ be {pnqn∣n∈N})\{p^nq^n \mid n \in N\}). Then which of the following is ALWAYS regular?
Official PYQ2011Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
A deterministic finite automaton (DFA\text{DFA}) DD with alphabet Σ={a,b}\Sigma = \{a, b\} is given below. Which of the following finite state machines is a valid minimal DFA\text{DFA} which accepts the same languages as DD?
Official PYQ2011Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
Definition of a language LL with alphabet {a}\{a\} is given as following.L={ank∣k>0,  and  n is a positive integer constant}L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}What is the minimum number of states needed in a DFA to recognize LL?
Official PYQ2011Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Consider the languages L1, L2 and L3L1, \:L2 \:and \: L3 as given below. L1={0p1q∣p,q∈N},L2={0p1q∣p,q∈N and p=q} and,L3={0p1q0r∣p,q,r∈N and p=q=r}.L1=\{0^p 1^q \mid p, q \in N\}, \\ L2 = \{0^p 1^q \mid p, q \in N \:and \:p=q\} \: and, \\ L3 = \{0^p 1^q 0^r \mid p, q, r \in N\: and \: p=q=r\}. Which of the following statements is NOT TRUE?
Official PYQ2011Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
Which of the following pairs have DIFFERENT expressive power?
Official PYQ2010Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
Let ww be any string of length nn in {0,1}∗\{0,1\}^*. Let LL be the set of all substrings of ww. What is the minimum number of states in non-deterministic finite automation that accepts LL?
Official PYQ2010Theory of ComputationContext-free Grammars and Push-down AutomataMCQ · 1 mark
Consider the languages L1={0i1j ∣i≠j},L1=\{0^i1^j\ \mid i \neq j\}, L2={0i1j∣i=j},L2=\{0^i1^j\mid i=j\}, L3={0i1j∣i=2j+1},L3=\{0^i1^j \mid i=2j+1\}, L4={0i1j∣i≠2j}L4=\{0^i1^j \mid i\neq2j\}
Official PYQ2010Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
Let L={w∈ (0+1)∗∣w has even number of 1s}L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}. i.e., LL is the set of all the bit strings with even numbers of 11s. Which one of the regular expressions below represents LL?
Official PYQ2010Theory of ComputationUndecidabilityMCQ · 1 mark
Let L1L_1 be the recursive language. Let L2L_2 and L3L_3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
Official PYQ2009Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
The above DFA accepts the set of all strings over {0,1}\{0,1\} that
Official PYQ2009Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Let L=L1∩L2L = L_1 \cap L_2, where L1L_1 and L2L_2 are languages as defined below: L1={ambmcanbn∣m,n≥0}L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \} L2={aibjck∣i,j,k≥0}L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \} Then LL is
Official PYQ2009Theory of ComputationContext-free Grammars and Push-down AutomataMCQ · 1 mark
Which one of the following is FALSE?
Official PYQ2009Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
Which one of the following languages over the alphabet {0,1}\{0,1\} is described by the regular expression: (0+1)∗0(0+1)∗0(0+1)∗(0+1)^*0(0+1)^*0(0+1)^*?
Official PYQ2009Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Let πA\pi_A be a problem that belongs to the class NP. Then which one of the following is TRUE?
Official PYQ2009Theory of ComputationContext-free Grammars and Push-down AutomataMCQ · 1 mark
S→aSa∣bSb∣a∣bS \to aSa \mid bSb\mid a\mid b The language generated by the above grammar over the alphabet {a,b}\{a,b\} is the set of:
Official PYQ2008Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Which of the following are regular sets? {anb2m∣n≥0,m≥0}\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\} {anbm∣n=2m}\left\{a^nb^m \mid n =2m \right\} {anbm∣n≠m}\left\{a^nb^m \mid n \neq m \right\} {xcy∣x,y,∈{a,b}∗}\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}
Official PYQ2008Theory of ComputationRegular Expressions and Finite AutomataMCQ · 1 mark
Match the following NFAs with the regular expressions they correspond to: P Q R S ϵ+0(01∗1+00)∗01∗\epsilon + 0\left(01^*1+00\right)^*01^* ϵ+0(10∗1+00)∗0\epsilon + 0\left(10^*1+00\right)^*0 ϵ+0(10∗1+10)∗1\epsilon + 0\left(10^*1+10\right)^*1 ϵ+0(10∗1+10)∗10∗\epsilon + 0\left(10^*1+10\right)^*10^*
Official PYQ2008Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Match the following: …
Official PYQ2008Theory of ComputationUndecidabilityMCQ · 1 mark
Which of the following statements is false?