QuestionPapersHub.com

Theory of Computation (TOC)

GATE-2019

Q:   If L is a regular language over Σ=(a,b), which one of the following languages is NOT regular ?

  • A:  L⋅LR={xy|x∈L,yR∈L}
  • B:  {wwR=|w∈L}
  • C:  Prefix (L)={x∈Σ∗|∃y∈Σ∗ such that xy∈L}
  • D:  Suffix (L)={y∈Σ∗|∃x∈Σ∗ such that xy∈L}
GATE-2019

Q:   For Σ={a,b}, let us consider the regular language L={x|x=a2+3k or x=b10+12k,k≥0. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L ? ________.

  • A:  3
  • B:  5
  • C:  9
  • D:  24
GATE-2019

Q:   Which one of the following languages over ∑={a,b} is NOT context-free?

  • A:  {wwR|w∈{a,b}∗}
  • B:  {wanbnwR|w∈{a,b}∗,n≥0}
  • C:  {wanwRbn|w∈{a,b}∗,n≥0}
  • D:  {anbi|i∈{n,3n,5n},n≥0}
GATE-2019

Q:   Consider the following sets:
S1. Set of all recursively enumerable languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet {0,1}
S4. Set of all non-regular languages over the alphabet {0,1}
Which of the above sets are uncountable?

  • A:  S1 and S2
  • B:  S3 and S4
  • C:  S2 and S3
  • D:  S1 and S4
GATE-2018

Q:   Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

  • A:  k≥2n
  • B:  k≥n
  • C:  k≤n2
  • D:  k≤2n
GATE-2018

Q:   The set of all recursively enumerable languages is

  • A:  closed under complementation.
  • B:  closed under intersection.
  • C:  a subset of the set of all recursive languages.
  • D:  an uncountable set.
GATE-2018

Q:   Which one of the following statements is FALSE?

  • A:  Context-free grammar can be used to specify both lexical and syntax rules.
  • B:  Type checking is done before parsing.
  • C:  High-level language programs can be translated to different Intermediate Representations.
  • D:  Arguments to a function can be passed using the program stack.
GATE-2018

Q:   Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.
(I) For an unrestricted grammar G and a string w, whether w∈L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammars G1 and G2, whether L(G1) = L(G2)
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.
Which one of the following statements is correct?

  • A:  Only I and II are undecidable
  • B:  Only III is undecidable
  • C:  Only II and IV are undecidable
  • D:  Only I, II and III are undecidable
GATE-2017

Q:   Consider the language L given by the regular expression (a+b)*b (a+b) over the alphabet {a,b}. The smallest number of states needed in a deteninistic finite-state automaton (DFA) accepting L is __________.

GATE-2017

Q:   If G is a grammar with productions
S→SaS|aSb|bSa|SS|∈
where S is the start variable, then which one of the following strings is not generated by G?

  • A:  abab
  • B:  aaab
  • C:  abbaa
  • D:  babba
1