ISRO CS Theory of Computation and Compiler Design PYQs: 7 Solved Questions

Theory of Computation and Compiler Design questions in ISRO CS often test whether you can separate definitions that look almost identical: grammar type versus language type, one derivation versus two parse trees, parser direction versus parser family, and a compiler optimisation versus the analysis that supports it.

Below are seven exact ISRO previous-year questions with their original options, correct answers and worked explanations.

For the full preparation route, use the ISRO Scientist/Engineer SC Computer Science course and the ISRO preparation hub.

Identify the deciding definition first

• Regular grammar: all productions follow one consistent linear direction.

• Palindrome grammar: inspect the base cases and how many symbols recursion adds.

• Ambiguity: one terminal string must have at least two distinct parse trees.

• Turing-machine run: the outcomes are accept, reject or continue forever.

• Top-down parser: it expands from the start symbol toward the input.

• Peephole optimisation: it examines a small contiguous instruction window.

• Incremental compilation: it recompiles only changed portions and their dependants.

1. Classifying a grammar — ISRO CS 2016

Question

What is the highest type number that can be assigned to the following grammar?

S → Aa

A → Ba

B → abc

• (A) Type 0

• (B) Type 1

• (C) Type 2

• (D) Type 3

Correct answer: (D) Type 3

Explanation

The productions are left-linear: when a non-terminal appears on the right, it is at the left end, as in S → Aa and A → Ba. The final rule contains terminals only. This is a regular grammar, which is Type 3 in the Chomsky hierarchy.

The grammar is also technically included in Types 2, 1 and 0 because the classes are nested. The phrase highest type number asks for the tightest classification, so Type 3 is the answer.

2. Language generated by a palindrome grammar — ISRO CS 2016

Question

S → aSa | bSb | a | b

The language generated by the above grammar over the alphabet {a, b} is the set of:

• (A) all palindromes

• (B) all odd length palindromes

• (C) strings that begin and end with the same symbol

• (D) all even length palindromes

Correct answer: (B) All odd length palindromes

Explanation

The base productions S → a and S → b generate palindromes of length one. Every recursive step adds the same symbol to both ends, increasing the length by two while preserving symmetry.

For example, S ⇒ aSa ⇒ abSba ⇒ ababa. Since the process starts with an odd length and always adds two, every generated string has odd length. There is no ε or two-symbol base production, so even-length palindromes cannot be generated.

3. Definition of an ambiguous grammar — ISRO CS 2020

Question

A given grammar is called ambiguous if:

• (A) two or more productions have the same non-terminal on the left hand side

• (B) a derivation tree has more than one associated sentence

• (C) there is a sentence with more than one derivation tree corresponding to it

• (D) brackets are not present in the grammar

Correct answer: (C) There is a sentence with more than one derivation tree corresponding to it

Explanation

Ambiguity is a property of the grammar when at least one terminal string has two distinct parse trees. For the familiar grammar E → E + E | E * E | id, the string id + id * id can receive different structures unless precedence is encoded.

Several productions sharing a left-hand non-terminal is normal in a context-free grammar and does not prove ambiguity. The test is not how many rules exist; it is whether one completed string can be parsed in more than one structurally different way.

4. Possible Turing-machine outcomes — ISRO CS 2014

Question

Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?

• (A) it may halt and accept the input

• (B) it may halt by changing the input

• (C) it may halt and reject the input

• (D) it may never halt

Correct answer: (B) It may halt by changing the input

Explanation

A Turing-machine computation has three possible outcomes: it can halt and accept, halt and reject, or run forever. The machine may rewrite tape symbols during its computation, but changing the tape is an action, not a terminal outcome.

Option B therefore describes something that can happen during execution rather than how the execution finishes. This wording trap disappears once you list the three outcomes before evaluating the options.

5. Recognising a top-down parser — ISRO CS 2015

Question

Which one of the following is a top-down parser?

• (A) Recursive descent parser

• (B) Shift left associative parser

• (C) SLR(k) parser

• (D) LR(k) parser

Correct answer: (A) Recursive descent parser

Explanation

A recursive descent parser starts with the grammar's start symbol and uses procedures corresponding to non-terminals. It expands productions from the root toward the leaves, so it belongs to the top-down family.

SLR and LR parsers are bottom-up shift-reduce parsers. They begin with the input and reduce substrings toward the start symbol, effectively constructing a rightmost derivation in reverse.

6. Peephole optimisation — ISRO CS 2011

Question

Which of the following statements about peephole optimization is False?

• (A) It is applied to a small part of the code

• (B) It can be used to optimize intermediate code

• (C) To get the best out of this, it has to be applied repeatedly

• (D) It can be applied to the portion of the code that is not contiguous

Correct answer: (D) It can be applied to the portion of the code that is not contiguous

Explanation

A peephole optimiser examines a short contiguous window of instructions. Inside that window it can remove redundant operations, replace expensive sequences or simplify jumps. The pass may be repeated because one rewrite can expose another opportunity.

The word peephole is the memory aid: the optimiser sees only a small neighbouring region at a time. Non-contiguous, whole-program relationships need broader data-flow or global analysis.

7. Incremental compilation — ISRO CS 2018

Question

Incremental-Compiler is a compiler

• (A) which is written in a language that is different from the source language

• (B) compiles the whole source code to generate object code afresh

• (C) compiles only those portion of source code that have been modified

• (D) that runs on one machine but produces object code for another machine

Correct answer: (C) Compiles only those portion of source code that have been modified

Explanation

An incremental compiler avoids rebuilding an unchanged program from scratch. It identifies modified source units and recompiles those units, together with anything whose generated result depends on them.

Option B describes a clean full rebuild. Option D describes a cross compiler, where the host and target machines differ. Option A does not define incremental behaviour.

Common traps in these ISRO TOC and Compiler PYQs

Continue with the ISRO CS DBMS solved PYQs and the ISRO CS Operating Systems PYQ guide for more subject-wise practice.

A compact revision routine

Attempt all seven questions again without reading the explanations. For each mistake, write one deciding rule: Type 3 is regular, the base decides palindrome parity, ambiguity requires two parse trees, a Turing machine accepts, rejects or loops, recursive descent is top-down, a peephole is contiguous, and incremental means changed portions only.

Then solve the options again. The purpose is to recognise the tested definition before distractors pull you toward a related but different term.