UTpaper

Free mock tests & test series

CIL MT · Computer Science

Theory of Computation & Compilers Previous Year Questions

27 Theory of Computation & Compilers (Computer Science) questions asked in CIL MT previous year papers, each with the correct answer and explanation. Read them free on UTpaper, or attempt the full papers as timed online tests.

  • 27 questions
  • Official answer key
  • Free
Attempt CIL MT papers →All Computer Science questions

Other Computer Science topics

Data Structures 56DBMS & SQL 53Digital Logic & Number Systems 26Computer Networks 22Operating Systems 21Algorithms 16Computer Organization & Architecture 16Programming in C/C++ 11Discrete Mathematics 10
Q1CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
Consider the following grammar G: E → T E' E' → + T E' ε T → F T' T' → * F T' ε F → (E) id Which of the following statements about top-down parsing of grammar G is true?
  1. AThe grammar is not left-recursive and can be parsed using a predictive (LL(1)) parser.
  2. BThe grammar requires backtracking since FIRST and FOLLOW sets of E’ overlap.
  3. CThe grammar is left-recursive and hence cannot be used for top-down parsing.
  4. DThe grammar is suitable for LL(1) (predictive) parsing and does not require backtracking.
Show answerHide answer

Correct answer: (D) The grammar is suitable for LL(1) (predictive) parsing and does not require backtracking.

Q2CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
In a shift-reduce parser, which of the following lists includes all four possible parser actions?
  1. AShift, Jump, Reduce, Halt
  2. BShift, Move, Accept, Reject
  3. CReduce, Copy, Accept, Abort
  4. DShift, Reduce, Accept, Error
Show answerHide answer

Correct answer: (D) Shift, Reduce, Accept, Error

Q3CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
In the grammar S→aS∣bS∣ϵ, which strings belong to the language?
  1. AOnly “ab” and “ba”
  2. BAny string of a’s and b’s
  3. COnly “a” and “b”
  4. Dstring of “ab” or “ba”
Show answerHide answer

Correct answer: (B) Any string of a’s and b’s

Q4CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
In the context of programming languages, if a compiler can determine the scope of a declaration by examining the program text alone, the language is said to use:
  1. ADynamic policy and lexical scope
  2. BStatic policy and lexical scope
  3. CStatic policy and dynamic scope
  4. DDynamic policy and dynamic scope
Show answerHide answer

Correct answer: (B) Static policy and lexical scope

Q5CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
______________________ is NOT a valid token typically generated by a lexical analyzer.
  1. AParser
  2. BCompiler
  3. CKeyword
  4. DVariable
Show answerHide answer

Correct answer: (A) Parser

Q6CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
A system must recognize any number of consecutive 'a's. Which regular expression correctly models this?
  1. Aa?
  2. Ba*
  3. Ca+
  4. Dab*
Show answerHide answer

Correct answer: (B) a*

Q7CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
Consider an FSM that accepts all strings over {a, b} with an even number of a’s. Which regular expression corresponds to it?
  1. A(a+b)∗a(a+b)∗(a+b)
  2. B(b∗(ab∗ab∗))∗
  3. C(a+b)∗a(a+b)∗(b+c)
  4. D(b∗ab∗)∗
Show answerHide answer

Correct answer: (B) (b∗(ab∗ab∗))∗

Q8CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
Which technique is commonly used by a compiler to recognize identifiers in a programming language?
  1. AHigh-level code optimization
  2. BRegular expressions and finite automata
  3. CManual code scanning
  4. DContext-free grammar
Show answerHide answer

Correct answer: (B) Regular expressions and finite automata

Q9CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
The minimized Deterministic Finite State Machine (DFSM) in theory of computation for a language always has:
  1. AExactly one final state
  2. BEqual number of final and non-final states
  3. CThe same number of states as the NFA
  4. DThe minimum number of states possible for that language
Show answerHide answer

Correct answer: (D) The minimum number of states possible for that language

Q10CIL MT Systems, 24 Aug 2026 (3:00 PM, CBT-26)
LR Parsing is known for being:
  1. ATop-down parsing
  2. BNon-deterministic always
  3. CLeft-recursive only
  4. DBottom-up parsing
Show answerHide answer

Correct answer: (D) Bottom-up parsing

Q11CIL MT Systems, 26 Mar 2017 (12:30 PM)
What will be the "First" and "Follow" of E and F for the following grammar? E -> TE' E' -> +TE' / ε T -> FT' T' -> *FT' / ε F -> id / (E)
  1. AFirst(E)={id, (, ε}, Follow(E)={ε, )}, First(F)={id, ), $}, Follow(F)={*, $, (}
  2. BFirst(E)={id, (}, Follow(E)={$, )}, First(F)={id, (}, Follow(F)={*, $, ), +}
  3. CFirst(E)={id, ), ε}, Follow(E)={ε, )}, First(F)={id, )}, Follow(F)={*, $, (, +}
  4. DFirst(E)={id, )}, Follow(E)={$, )}, First(F)={id, (, $}, Follow(F)={*, $, ), +}
Show answerHide answer

Correct answer: (B) First(E)={id, (}, Follow(E)={$, )}, First(F)={id, (}, Follow(F)={*, $, ), +}

Q12CIL MT Systems, 26 Mar 2017 (12:30 PM)
Which of the following statements is TRUE for the grammar given below? S -> (L) / a L -> L,S / S
  1. AThe grammar can be parsed by LR(0) parser only
  2. BThe grammar can be parsed by LR(0) and SLR(1) parsers
  3. CThe grammar can be parsed by LL(1) parser only
  4. DThe grammar can be parsed by LL(1) and LR(0) parsers
Show answerHide answer

Correct answer: (B) The grammar can be parsed by LR(0) and SLR(1) parsers

Q13CIL MT Systems, 26 Mar 2017 (12:30 PM)
If every production is of the form α → β where |α| ≤ |β| or of the form α → λ, then the grammar is said to be of:
  1. AType 3
  2. BType 1
  3. CType 0
  4. DType 2
Show answerHide answer

Correct answer: (B) Type 1

Q14CIL MT Systems, 26 Mar 2017 (12:30 PM)
Let L be the language on A = {a, b, c} which consists of all words of the form w = aʳbˢcᵗ where r, s, t > 0. Which of the following is the valid regular expression 'r' such that L = L(r)?
  1. Ar = a*b*c*
  2. Br = aa*bb*c*
  3. Cr = aa*b*cc*
  4. Dr = aa*bb*cc*
Show answerHide answer

Correct answer: (D) r = aa*bb*cc*

Q15CIL MT Systems, 27 Feb 2020 (8:00 AM)
Consider the following problem X "Given a Turing Machine M over the input alphabet Σ any state q of M and word w in Σ*, does the computation of M on w visit the state q" Which of the following X is correct?
  1. AX is undecidable but partially decidable
  2. BX is not a decision problem
  3. CX is decidable
  4. DX is undecidable but not even partially decidable
Show answerHide answer

Correct answer: (A) X is undecidable but partially decidable

Q16CIL MT Systems, 27 Feb 2020 (8:00 AM)
Consider the following grammar S → m | mn | mno Choose correct statement from the following:
  1. AThe grammar is LL(4)
  2. BThe grammar is LL(3)
  3. CThe grammar is LL(2)
  4. DThe grammar is LL(1)
Show answerHide answer

Correct answer: (B) The grammar is LL(3)

Q17CIL MT Systems, 27 Feb 2020 (8:00 AM)
Generation of intermediate code based on an abstract machine model is useful in compilers because:
  1. AIt makes implementation of lexical and syntax analysis easier
  2. BIt is difficult to generate executable code from high level language program.
  3. CSyntax translations are easier for intermediate code generation
  4. DIt enhances the portability of the compiler system program
Show answerHide answer

Correct answer: (A) It makes implementation of lexical and syntax analysis easier

Q18CIL MT Systems, 27 Feb 2020 (8:00 AM)
Which is equivalent CFG without useless symbols for the given grammar: S → PQ | p , P → p
  1. AS → PQ
  2. BS → p
  3. CS → P , P → p
  4. DS → P | p , P → p
Show answerHide answer

Correct answer: (B) S → p

Q19CIL MT Systems, 27 Feb 2020 (8:00 AM)
Which of the following derivation does a top-down parser use while parsing a input string? The input is assumed to be scanned in left to right order.
  1. ATopmost derivation
  2. BLeftmost derivation traced out in reverse
  3. CLeftmost derivation
  4. DRightmost derivation
Show answerHide answer

Correct answer: (C) Leftmost derivation

Q20CIL MT Systems, 27 Feb 2020 (8:00 AM)
Which of the following statement is true?
  1. AThe parsers canonical LR and LALR have the same power
  2. BLALR parser is more important than canonical LR parser
  3. CSLR parser is more powerful than LALR parser
  4. DCanonical LR parser is more powerful than LALR parser
Show answerHide answer

Correct answer: (D) Canonical LR parser is more powerful than LALR parser

Q21CIL MT Systems, 27 Feb 2020 (8:00 AM)
The language generated by following grammar is: S → aSa | bSb | ε
  1. AEven length palindrome
  2. Ba^m b^n, n ≥ 0, m ≥ 0
  3. COdd length palindrome
  4. Da^n b^m, n ≥ 1, m ≥ 1
Show answerHide answer

Correct answer: (A) Even length palindrome

Q22CIL MT Systems, 27 Feb 2020 (8:00 AM)
The language {a^m b^n c^(m+n) | m, n ≥ 1} is:
  1. Aregular
  2. Btype 0 but not context sensitive
  3. Ccontext free but not regular
  4. Dcontext sensitive but not context free
Show answerHide answer

Correct answer: (C) context free but not regular

Q23CIL MT Systems, 27 Feb 2020 (8:00 AM)
Which of the following statement is false?
  1. AEvery regular language is also a context free language
  2. BEvery non deterministic Turing machine can be converted to an equivalent deterministic Turing machine
  3. CEvery subset of recursively enumerable set is recursive.
  4. DEvery NFA can be converted into equivalent DFA
Show answerHide answer

Correct answer: (C) Every subset of recursively enumerable set is recursive.

Q24CIL MT Systems, 27 Feb 2020 (8:00 AM)
Consider the grammar S → AbBaCc | ε A → aAb | ba B → bBC | cb C → cCa | ac Find the First ( ) of S
  1. A{a, b, ε}
  2. B{ε}
  3. C{a, ε}
  4. D{a, b, c, ε}
Show answerHide answer

Correct answer: (A) {a, b, ε}

Q25CIL MT Systems, 27 Feb 2020 (8:00 AM)
Which one of the following is True?
  1. AEvery regular grammar is LL(1) and every regular set does not have an LR(1) grammar
  2. BEvery regular grammar is not LL(1) and every regular set does not have an LR(1) grammar
  3. CEvery regular grammar is LL(1) and every regular has an LR(1) grammar
  4. DEvery regular grammar is not LL(1) and every regular set has an LR(1) grammar
Show answerHide answer

Correct answer: (D) Every regular grammar is not LL(1) and every regular set has an LR(1) grammar

Q26CIL MT Systems, 27 Feb 2020 (8:00 AM)
Number of states in DFA accepting the following language is: L = { a^n b^(2m) | n, m ≥ 1 }
  1. Am
  2. Bn
  3. C5
  4. D2
Show answerHide answer

Correct answer: (C) 5

Q27CIL MT Systems, 27 Feb 2020 (8:00 AM)
Which of following problems are undecidable? I. Membership problem in context-free languages II. Whether a given context-free language is regular III. Whether a finite state automation halts on all inputs IV. Membership problem for type 0 languages
  1. AIII and IV
  2. BI and IV
  3. CI and II
  4. DII and IV
Show answerHide answer

Correct answer: (D) II and IV

How to use these CIL MT Computer Science questions

Every question here was asked in a real CIL MT paper; the paper and shift are shown on the card, and the number opens the question on its own page. Try each one before tapping Show answer, then attempt the full CIL MT papers as timed tests to check your speed under exam conditions.

More CIL MT subjects

English 75General Awareness 75Mathematics 75Reasoning 64