UGC NET Computer Science Theory of Computation and Compilers Previous Year Questions (PYQs)

All 46 Theory of Computation and Compilers PYQs

Ordered newest exam first. Each question links back to the full paper it came from.

1. Question 1

   UGC NET January 2025

   The kinds of symbols for basic syntactic elements of first-order logic are:

   A. Constant
   B. Domain
   C. Predicate
   D. Temporal
   E. Function

   1. AB and D only
   2. BA, B and C only
   3. CA, C and E only
   4. DC and D only

   Answer: (C) A, C and E only

   Explanation

   Constants, predicates and functions are object-language symbols in first-order logic. A domain is part of the interpretation and “temporal” is not a basic first-order syntactic symbol. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

2. Question 2

   UGC NET January 2025

   Which statement is true about the pumping lemma for regular languages?

   1. AIt applies to all regular languages
   2. BIt applies only to infinite regular languages
   3. CIt applies to all context-free languages
   4. DIt applies to all recursively enumerable languages

   Answer: (A) It applies to all regular languages

   Explanation

   Every regular language satisfies the pumping-lemma property. The lemma is chiefly useful for proving that a language is not regular when sufficiently long strings are considered; it does not apply to arbitrary context-free or recursively enumerable languages.

   Sign in to read the full explanation

   Sign in

3. Question 3

   UGC NET January 2025

   Regarding code optimisation, choose the correct sequence.

   A. Algebraic simplification
   B. Use of machine idioms
   C. Redundant-instruction elimination
   D. Flow-of-control optimisation
   E. Improved target code

   1. AA, C, B, D, E
   2. BB, C, D, A, E
   3. CC, D, A, B, E
   4. DD, B, A, C, E

   Answer: (C) C, D, A, B, E

   Explanation

   The standard optimisation progression removes redundant instructions, improves flow of control, performs algebraic simplification, uses machine idioms, and yields improved target code. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

4. Question 4

   UGC NET January 2025

   Match List-I with List-II.

   List-I	List-II
   A. Conflict resolution B. Common subexpression C. Quadruples D. L-attributed definitions	I. Three-address code II. Precedence III. Syntax-directed translations IV. Directed acyclic graph

   1. AA-III, B-II, C-IV, D-I
   2. BA-II, B-IV, C-I, D-III
   3. CA-II, B-III, C-I, D-IV
   4. DA-IV, B-I, C-II, D-III

   Answer: (B) A-II, B-IV, C-I, D-III

   Explanation

   Conflict resolution uses precedence, a common subexpression is represented by a DAG, quadruples are a three-address-code representation, and L-attributed definitions are syntax-directed translations.

   Sign in to read the full explanation

   Sign in

5. Question 5

   UGC NET January 2025

   Which of the following CFG(s) is/are in Chomsky Normal Form? All capital letters are variables and lower-case letters are terminals.

   Grammar	Productions
   A	S → ABC | AB; A → a; B → b; C → d
   B	X → RT | TR; T → l; R → XT | r
   C	P → qP | sQ; M → MN | MP
   D	N → nmin; P → P

   1. AA and B only
   2. BB only
   3. CC only
   4. DB and D only

   Answer: (B) B only

   Explanation

   CNF permits a variable to produce two variables, or a single terminal. Grammar B meets that requirement; A has a three-variable right-hand side, C combines a terminal and variable, and D has invalid productions.

   Sign in to read the full explanation

   Sign in

6. Question 6

   UGC NET January 2025

   Choose the correct statements.

   A. A problem which is NP-complete can be solved in polynomial time.
   B. All NP-complete problems are NP-hard problems.
   C. If an NP-hard problem can be solved in polynomial time, then all NP-complete problems can be solved in polynomial time.
   D. All NP-hard problems are not NP-complete.

   1. AA and C only
   2. BB and D only
   3. CA, B and C only
   4. DA, B, C and D

   Answer: (D) A, B, C and D

   Explanation

   NP-complete problems are NP-hard. A polynomial-time algorithm for any NP-hard problem would also put every NP-complete problem in P; NP-hard contains problems beyond NP-complete. Following the paper’s formulation, all four statements are selected.

   Sign in to read the full explanation

   Sign in

7. Question 7

   UGC NET January 2025

   Which language is represented by the displayed Turing-machine transition function?

   1. A{aⁿbⁿ | n ≥ 0}
   2. B{abⁿ | n ≥ 1}
   3. C{ab* | n > 0}
   4. D{aⁿb* | n > 1}

   Answer: (B) {abⁿ | n ≥ 1}

   Explanation

   The machine marks the initial a, scans and marks the corresponding b symbols, and accepts the resulting single-a followed by one-or-more-b pattern described by option B. The transition notation in the source page is diagrammatic, so this follows the official final key.

   Sign in to read the full explanation

   Sign in

8. Question 8

   UGC NET January 2025

   Match List-I with List-II.

   List-I	List-II
   A. Type-0 grammar B. Type-1 grammar C. Type-2 grammar D. Type-3 grammar	I. Linear grammar II. GNF III. x → y, |x| ≤ |y|; x,y ∈ (V ∪ T)* IV. Recursively enumerable

   1. AA-I, B-II, C-III, D-IV
   2. BA-II, B-I, C-III, D-IV
   3. CA-III, B-II, C-IV, D-I
   4. DA-IV, B-III, C-I, D-II

   Answer: (D) A-IV, B-III, C-I, D-II

   Explanation

   Type-0 grammars are recursively enumerable; Type-1 has noncontracting productions |x| ≤ |y|; Type-2 grammars can be in Greibach normal form; and Type-3 grammars are linear. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

9. Question 9

   UGC NET January 2025

   Yacc is which of the following parsers?

   1. APredictive parser
   2. BSLR parser
   3. CCLR parser
   4. DLALR parser

   Answer: (D) LALR parser

   Explanation

   Yacc generates LALR(1) parsers. It combines LR parsing power with compact tables relative to canonical LR parsing. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

10. Question 10

    UGC NET January 2025

    For the automaton described in the accompanying comprehension passage, which displayed diagram represents the minimum-state DFA?

    

    DFA options 1-4 for Question 141

    1. ADFA diagram 1
    2. BDFA diagram 2
    3. CDFA diagram 3
    4. DDFA diagram 4

    Answer: (D) DFA diagram 4

    Explanation

    The official final answer key marks this question as dropped, so no displayed DFA should be treated as a reliable scored answer. The source diagrams are attached for review and preservation of the original question.

    Sign in to read the full explanation

    Sign in

11. Question 11

    UGC NET January 2025

    For the automaton in the preceding comprehension passage, which displayed diagram is correct?

    

    DFA options 1-4 for Question 142

    1. ADFA diagram 1
    2. BDFA diagram 2
    3. CDFA diagram 3
    4. DDFA diagram 4

    Answer: (C) DFA diagram 3

    Explanation

    The official final answer key selects diagram 3. It has the required transition path to the accepting state and the loops needed to preserve acceptance after the target pattern has been recognized.

    Sign in to read the full explanation

    Sign in

12. Question 12

    UGC NET January 2025

    For the preceding automaton passage, which displayed DFA represents the language accepted by the machine?

    

    DFA options 1-4 for Question 143

    1. ADFA diagram 1
    2. BDFA diagram 2
    3. CDFA diagram 3
    4. DDFA diagram 4

    Answer: (C) DFA diagram 3

    Explanation

    The official final answer key selects diagram 3. Its transitions track the required substring while allowing arbitrary symbols before and after it, matching the language described in the passage.

    Sign in to read the full explanation

    Sign in

13. Question 13

    UGC NET January 2025

    For the automaton described in the comprehension passage, which regular expression represents its accepted language?

    1. A(a+b)*aab
    2. Baba(a+b)*
    3. Cb(a+b)*b(a+b)a(a+b)
    4. D(a+b)abb(a+b)

    Answer: (D) (a+b)abb(a+b)

    Explanation

    The official final key selects (a+b)*abb(a+b)*, i.e. all strings over {a,b} containing abb as a substring. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

    Sign in to read the full explanation

    Sign in

14. Question 14

    UGC NET January 2025

    For the automaton described in the comprehension passage, which grammar represents the language accepted by the machine?

    1. AS → AabbB, A → aA | ε, B → bB | ε
    2. BS → abbA, A → aA | ε | bA
    3. CS → AabbA, A → aA | bA | ε
    4. DS → Aabb, A → aA | bA | ε

    Answer: (C) S → AabbA, A → aA | bA | ε

    Explanation

    Option C generates all strings over {a,b} that contain abb as a substring, matching the regular expression selected for the same passage. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

    Sign in to read the full explanation

    Sign in

15. Question 15

    UGC NET August 2024

    Consider the grammar:

    S → A
    A → $B$ | id
    B → B, A | A

    If I₀ = CLOSURE({[S → .A]}), how many items are in GOTO(I₀, $)?

    1. A3
    2. B4
    3. C5
    4. D6

    Answer: (C) 5

    Explanation

    GOTO(I₀, $) begins with A → $.B. Its closure adds B → .B, A, B → .A, A → .$B$, and A → .id, giving five items in total. Therefore option C is correct.

    Sign in to read the full explanation

    Sign in

16. Question 16

    UGC NET August 2024

    Consider the Grammar:
    T → Qx
    Q → RS
    R → y ∣ ϵ
    S → z ∣ ϵ
    Here x, y, z are terminals and T, Q, R, S are non-
    terminals.
    What will be the follow set of the non-terminal R?

    1. A{x,y}
    2. B{y,z}
    3. C{z,x}
    4. D{ϵ}

    Answer: (C) {z,x}

    Explanation

    In Q → RS, whatever can begin S follows R, contributing z. Because S can also derive ε, anything following Q follows R as well, and T → Qx supplies x. Hence FOLLOW(R) = {z, x}, which is option C.

    Sign in to read the full explanation

    Sign in

17. Question 17

    UGC NET August 2024

    Which of the following properties correctly
    describe a Regular Grammar ?
    A. All production rules are of the form A→xB or
    A→x, where A and B are non terminal symbols
    and x is a terminal symbol.
    B. Regular grammars are more powerful than
    context-free grammars and can express any type
    of language.
    C. There is a direct correspondence between
    regular grammar and finite automata.
    D. Regular grammars can generate languages
    that are not recognised by any type of automata.

    1. A(A) and (B) Only
    2. B(B) and (C) Only
    3. C(C) and (D) Only
    4. D(A) and (C) Only

    Answer: (D) (A) and (C) Only

    Explanation

    (A) is true: right-linear rules of the form A → xB or A → x define a regular grammar. (C) is true: every regular grammar has an equivalent finite automaton and vice versa. (B) is false — regular grammars are strictly weaker than context-free ones. (D) is false — the languages they generate are exactly those finite automata accept. Only (A) and (C), so option D.

    Sign in to read the full explanation

    Sign in

18. Question 18

    UGC NET August 2024

    If L₁ and L₂ are context free languages, which one of the following is true about L₁ ∩ L₂?

    1. AL1 L2 is context free.
    2. BL1 L2 is Regular
    3. CL1 L2 is Recursive Enumerable
    4. DL1 L2 is Context Sensitive

    Answer: (C) L1 L2 is Recursive Enumerable

    Explanation

    Context-free languages are not closed under intersection, so L₁ ∩ L₂ need not be context-free, and it certainly need not be regular. Both languages are recursive and therefore recursively enumerable, and that class is closed under intersection, so the intersection is guaranteed to be recursively enumerable. Option C is the only statement that always holds.

    Sign in to read the full explanation

    Sign in

19. Question 19

    UGC NET August 2024

    Which of the following tasks could be attained
    using syntax trees in compiler design ?
    A. Type Checking
    B. Code Generation
    C. Code Optimization
    D. Error Handling

    1. A(A), (B), (C) Only
    2. B(B), (C), (D) Only
    3. C(A), (C), (D) Only
    4. D(A), (B), (D) Only

    Answer: (A) (A), (B), (C) Only

    Explanation

    A syntax tree is the structured representation the compiler walks for type checking (A), code generation (B) and code optimisation (C). It can reveal that an error exists, but recovering from errors is the job of the error-handling machinery rather than the tree itself. Only (A), (B) and (C) — option A.

    Sign in to read the full explanation

    Sign in

20. Question 20

    UGC NET August 2024

    Match List-I with List-II.

    List-I	List-II
    (A) HTML	(I) Allow for dynamic and interactive web pages.
    (B) DHTML	(II) Defines the structure of web pages.
    (C) XML	(III) Object-oriented programming language for web applications.
    (D) JAVA	(IV) Used for data storage and transport.

    1. A(A)-(I), (B)-(III), (C)-(II), (D)-(IV)
    2. B(A)-(II), (B)-(III), (C)-(IV), (D)-(I)
    3. C(A)-(II), (B)-(I), (C)-(IV), (D)-(III)
    4. D(A)-(III), (B)-(I), (C)-(IV), (D)-(II)

    Answer: (C) (A)-(II), (B)-(I), (C)-(IV), (D)-(III)

    Explanation

    HTML defines page structure, so (A)-(II). DHTML adds dynamic, interactive behaviour, giving (B)-(I). XML carries and stores data, so (C)-(IV). Java is the object-oriented language used for web applications, so (D)-(III). Option C is correct.

    Sign in to read the full explanation

    Sign in

21. Question 21

    UGC NET August 2024

    Arrange the following stages of a Turing Machine
    (TM) operation in the correct order as they occur
    during computation.
    A. Writing a symbol on the tape
    B. Moving the tape head left to right
    C. Reading a symbol from the tape
    D. Transitioning to a new state based on the
    current state and symbol read
    E. Halting and accepting or rejecting the input

    1. A(C), (A), (B), (D), (E)
    2. B(C), (B), (A), (D), (E)
    3. C(C), (D), (A), (B), (E)
    4. D(C), (D), (B), (A), (E)

    Answer: (C) (C), (D), (A), (B), (E)

    Explanation

    One Turing machine step reads the symbol under the head (C), combines it with the current state to choose a transition (D), writes a symbol (A) and moves the head (B). The machine halts and accepts or rejects when no further transition applies (E). That order is option C.

    Sign in to read the full explanation

    Sign in

22. Question 22

    UGC NET August 2024

    Which of the following languages can be recognized by a Non-Deterministic Finite Automaton (NFA) but cannot be recognized by a Deterministic Finite Automaton (DFA)?

    A. L₁ = {w ∈ {0,1}* | the length of w is even}
    B. L₂ = {w ∈ {0,1}* | the length of w is odd}
    C. L₃ = {w ∈ {0,1}* | all 0s precede all 1s in w}
    D. L₄ = {w ∈ {0,1}* | w contains an equal number of 0s and 1s}
    E. L₅ = {w ∈ {0,1}* | all 1s precede all 0s in w}

    1. A(A) and (B) only
    2. B(B) and (C) only
    3. C(C) and (D) only
    4. DNone of the above

    Answer: (D) None of the above

    Explanation

    NFAs and DFAs recognize exactly the same regular languages. L₁, L₂, L₃, and L₅ are regular and recognized by both, while L₄ is non-regular and recognized by neither. Therefore option D is correct.

    Sign in to read the full explanation

    Sign in

23. Question 23

    UGC NET August 2024

    Arrange the following stages of parsing in the
    correct order as they typically occur in the
    compilation process.
    A. Lexical Analysis
    B. Sematic Analysis
    C. Syntax Analysis
    D. Intermediate Code Generation
    E. Code Optimization

    1. A(A), (B), (C), (D), (E)
    2. B(A), (C), (B), (D), (E)
    3. C(A), (D), (B), (C), (E)
    4. D(A), (C), (D), (B), (E)

    Answer: (B) (A), (C), (B), (D), (E)

    Explanation

    Compilation runs lexical analysis (A) to produce tokens, syntax analysis (C) to build the parse tree, semantic analysis (B) to check types and meaning, intermediate code generation (D), then code optimisation (E). That order is option B.

    Sign in to read the full explanation

    Sign in

24. Question 24

    UGC NET August 2024

    Arrange the following Language Classes in
    ascending order according to their expressive
    power, as defined by Chomsky hierarchy:
    A. Context-free languages
    B. Context-sensitive languages
    C. Regular languages
    D. Unrestricted Grammars

    1. A(C), (A), (B), (D)
    2. B(C), (A), (D), (B)
    3. C(A), (C), (B), (D)
    4. D(A), (D), (B), (C)

    Answer: (A) (C), (A), (B), (D)

    Explanation

    By expressive power the Chomsky hierarchy runs regular ⊂ context-free ⊂ context-sensitive ⊂ unrestricted, recognised respectively by finite automata, pushdown automata, linear bounded automata and Turing machines. Ascending order is therefore (C), (A), (B), (D) — option A.

    Sign in to read the full explanation

    Sign in

25. Question 25

    UGC NET August 2024

    Which of the following languages are context-free?

    A. {wⁱxʲyᵏzˡ | i + k = j + l; i, j, k, l ≥ 0}
    B. {wⁱxʲyᵏzˡ | i = j and k = l; i, j, k, l ≥ 0}
    C. {wⁱxʲyᵏzˡ | i = j = k and k ≠ l; i, j, k, l ≥ 0}
    D. {wⁱxʲyᵏzˡ | i = j = k + l; i, j, k, l ≥ 0}
    E. {wⁱxʲyᵏzˡ | i = j = l and k ≠ l; i, j, k, l ≥ 0}

    1. A(A) and (B) only
    2. B(B) and (C) only
    3. C(C) and (D) only
    4. D(D) and (E) only

    Answer: (A) (A) and (B) only

    Explanation

    Language A has one balance condition that can be handled by a stack, and language B is an intersection/concatenation of simple equality constraints expressible as a context-free language. The remaining languages impose simultaneous multi-count dependencies that are not context-free, so option A is correct.

    Sign in to read the full explanation

    Sign in
26. Practise Theory of Computation and Compilers in a timed set

27. Question 26

    UGC NET December 2023

    Let L={ab, aa, baa}. Which of the following strings are not in L*.

    1. Aabaabaaabaa
    2. Baaaabaaaa
    3. Cbaaaaabaaaab
    4. Dbaaaaabaa

    Answer: (C) baaaaabaaaab

    Explanation

    The key idea is stated in the problem: Let L={ab, aa, baa}. Which of the following strings are not in L*.. The correct answer is C: baaaaabaaaab. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

28. Question 27

    UGC NET December 2023

    Let A={a, b} and L=A*. Let x={a"b", n>0}. The languages L U X and X are respectively :

    1. ANot regular, Regular
    2. BRegular, Regular
    3. CRegular, Not regular
    4. DNot Regular, Not Regular

    Answer: (C) Regular, Not regular

    Explanation

    The key idea is stated in the problem: Let A={a, b} and L=A*. Let x={a"b", n>0}. The languages L U X and X are respectively :. The correct answer is C: Regular, Not regular. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

29. Question 28

    UGC NET December 2023

    Which of the following symbol table implementation is best suited if access time is to be minimum ?

    1. A_ Linear list
    2. BSearch tree
    3. CHash Table
    4. DSelf organisation list

    Answer: (C) Hash Table

    Explanation

    The key idea is stated in the problem: Which of the following symbol table implementation is best suited if access time is to be minimum ?. The correct answer is C: Hash Table. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

30. Question 29

    UGC NET December 2023

    Consider a Grammar E>E+n|ExXn|n for a sentence n+n Xn, the handles in the right-sentential form of the reduction are ?

    1. An,E+nandE+nxn
    2. Bn,E+nand E+Exn
    3. Cn,n+nandn+nxn
    4. Dn,E+nand Exn

    Answer: (D) n,E+nand Exn

    Explanation

    The key idea is stated in the problem: Consider a Grammar E>E+n|ExXn|n for a sentence n+n Xn, the handles in the right-sentential form of the reduction are ?. The correct answer is D: n,E+nand Exn. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

31. Question 30

    UGC NET December 2023

    One of the purposes of using intermediate code in compilers is to :

    1. Amake parsing and semantic analysis simpler
    2. Bimprove error recovery and error reporting
    3. Cincrease the chances of reusing the machine independent code optimizer in other compilers
    4. Dimprove the register allocation

    Answer: (C) increase the chances of reusing the machine independent code optimizer in other compilers

    Explanation

    The key idea is stated in the problem: One of the purposes of using intermediate code in compilers is to :. The correct answer is C: increase the chances of reusing the machine independent code optimizer in other compilers. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

32. Question 31

    UGC NET December 2023

    The sum of minimum and maximum number of final states for a Deterministic Finite Automata (DFA) having 'P" state is equal to : () Pp

    1. Ap
    2. Bp-1
    3. Cp+1
    4. Dp+2

    Answer: (C) p+1

    Explanation

    The key idea is stated in the problem: The sum of minimum and maximum number of final states for a Deterministic Finite Automata (DFA) having 'P" state is equal to : () Pp. The correct answer is C: p+1. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

33. Question 32

    UGC NET December 2023

    Three address codes can be represented in special structures known as :
    A. Quadruples
    B. Triples
    C. Patterns
    D. Indirect Triples Choose the correct answer from the options given below :

    1. A(A) and (B) Only
    2. B(A), (B) and (D) Only
    3. C(B) and (C) Only
    4. D(B), (Cand (D) Only

    Answer: (B) (A), (B) and (D) Only

    Explanation

    The key idea is stated in the problem: Three address codes can be represented in special structures known as :
    A. Quadruples
    B. Triples
    C. Patterns
    D. Indirect Triples Choose the correct answer from the options given below :. The correct answer is B: (A), (B) and (D) Only. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

34. Question 33

    UGC NET December 2023

    Which of the statement is/are CORRECT ?
    A. Moore and Mealy machines are finite state machines with output capabilities.
    B. Any given Moore machine has an equivalent Mealy machine.
    C. Any given Mealy machine has an equivalent Moore machine.
    D. Moore machine is not a finite state machine. Choose the correct answer from the options given below :

    1. A(A) and (B) Only
    2. B(A), (B) and (©) Only
    3. C(B) and (D) Only
    4. D(A), (B) and (D) Only

    Answer: (B) (A), (B) and (©) Only

    Explanation

    The key idea is stated in the problem: Which of the statement is/are CORRECT ?
    A. Moore and Mealy machines are finite state machines with output capabilities.
    B. Any given Moore machine has an equivalent Mealy machine.
    C. Any given Mealy machine has an equivalent Moore machine.
    D. Moore machine. The correct answer is B: (A), (B) and (©) Only. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

35. Question 34

    UGC NET December 2023

    Arrange the following phases of a compiler as per their order of execution (start to end)
    A. Target code generation
    B. Syntax Analysis
    C. Code optimization
    D. Semantic Analysis
    E. Lexical Analysis Choose the correct answer from the options given below :

    1. A(B), (B), (D), (A), ©)
    2. B(&), (D), @), (A), (©
    3. C(&), (B), (D), (©), (A)
    4. D(B), (D), (E), (A), ©)

    Answer: (C) (&), (B), (D), (©), (A)

    Explanation

    The key idea is stated in the problem: Arrange the following phases of a compiler as per their order of execution (start to end)
    A. Target code generation
    B. Syntax Analysis
    C. Code optimization
    D. Semantic Analysis
    E. Lexical Analysis Choose the correct answer from the options given below :. The correct answer is C: (&), (B), (D), (©), (A). It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

36. Question 35

    UGC NET December 2023

    The prototyping model has the sequence :
    A. Customer Evaluation
    B. Quick design
    C. Requirements
    D. Implement
    E. Design Choose the correct answer from the options given below :

    1. AC → A → D → B → E
    2. BB → C → A → D → E
    3. CC → B → D → A → E
    4. DE → B → C → D → A

    Answer: (C) C → B → D → A → E

    Explanation

    The key idea is stated in the problem: The prototyping model has the sequence :
    A. Customer Evaluation
    B. Quick design
    C. Requirements
    D. Implement
    E. Design Choose the correct answer from the options given below :. The correct answer is C: C → B → D → A → E. It follows the governing definition, algorithm, or calculation in this theory of computation and compilers item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

37. Question 36

    UGC NET November 2020

    Consider L = L₁ ∩ L₂, where L₁ = {0ᵐ1ᵐ20ⁿ1ⁿ | m, n ≥ 0} and L₂ = {0ᵐ1ⁿ2ᵏ | m, n, k ≥ 0}. Then L is

    1. ARecursively enumerable but not context-free
    2. BRegular
    3. CContext-free but not regular
    4. DNot recursive

    Answer: (C) Context-free but not regular

    Explanation

    For a string to be in both languages, the portion after 2 in L₁ must be empty and the number of 1s before 2 must equal the number of 0s. Thus L reduces to {0ᵐ1ᵐ2 | m ≥ 0}, which is context-free but not regular.

    Sign in to read the full explanation

    Sign in

38. Question 37

    UGC NET November 2020

    Let L₁ and L₂ over Σ = {a, b} be represented by (a* + b)* and (a + b)* respectively. Which statement is true?

    1. AL₁ ⊂ L₂
    2. BL₂ ⊂ L₁
    3. CL₁ = L₂
    4. DL₁ ∩ L₂ = ∅

    Answer: (C) L₁ = L₂

    Explanation

    The inner expression a* + b can generate either any run of a characters or a single b. Repeating it with the outer star generates every string over {a, b}, exactly as (a + b)* does. Therefore L₁ = L₂; neither language excludes a mixed a/b string.

    Sign in to read the full explanation

    Sign in

39. Question 38

    UGC NET November 2020

    Which statement is true?

    1. AThe union of two context-free languages is context-free.
    2. BThe intersection of two context-free languages is context-free.
    3. CThe complement of a context-free language is context-free.
    4. DEvery context-free language can be accepted by a deterministic pushdown automaton.

    Answer: (A) The union of two context-free languages is context-free.

    Explanation

    Context-free languages are closed under union. They are not closed under intersection or complement, and deterministic PDAs recognise only the smaller class of deterministic context-free languages.

    Sign in to read the full explanation

    Sign in

40. Question 39

    UGC NET November 2020

    Which of the following is not an intermediate code form?

    1. ASyntax trees
    2. BThree-address codes
    3. CQuadruples
    4. DPostfix notation

    Answer: (A) Syntax trees

    Explanation

    Three-address code, quadruples, and postfix notation are linear intermediate-code representations used in translation. A syntax tree is a structural representation of the parsed program rather than an intermediate code sequence.

    Sign in to read the full explanation

    Sign in

41. Question 40

    UGC NET November 2020

    Which of the following are applications of a compiler symbol table?
    A. Storage allocation
    B. Checking type compatibility
    C. Suppressing duplicate-error messages

    1. A(A) and (B) only
    2. B(A) and (C) only
    3. C(B) and (C) only
    4. D(A), (B), and (C)

    Answer: (D) (A), (B), and (C)

    Explanation

    A symbol table records identifiers and their attributes. Compilers consult it for storage allocation and type checking, and it also lets them recognise a repeated declaration so duplicate diagnostics are controlled. Thus all three listed uses apply.

    Sign in to read the full explanation

    Sign in

42. Question 41

    UGC NET November 2020

    Let G₁ and G₂ be arbitrary context-free grammars and R an arbitrary regular language. Which problems are undecidable?
    A. Is L(G₁) = L(G₂)?
    B. Is L(G₁) ⊂ L(G₂)?
    C. Is L(G₁) = R?

    1. A(A) only
    2. B(B) only
    3. C(A) and (B) only
    4. D(A), (B), and (C)

    Answer: (D) (A), (B), and (C)

    Explanation

    Equivalence and proper inclusion for arbitrary context-free languages are undecidable. Equality with a regular language is also undecidable: choosing R = Σ* would decide the undecidable universality problem for context-free grammars.

    Sign in to read the full explanation

    Sign in

43. Question 42

    UGC NET November 2020

    Consider the languages

    L₁ = {aᶻ | z is an integer},
    L₂ = {a²ᶻ | z > 0}, and
    L₃ = {ww | w ∈ {a,b}*}.

    Which are regular?

    1. AL₁ and L₂ only
    2. BL₁ and L₃ only
    3. CL₂ only
    4. DL₃ only

    Answer: (A) L₁ and L₂ only

    Explanation

    The first two languages are unary languages described by simple length patterns and are regular. The copy language {ww} requires matching an arbitrary string with itself, which is not regular.

    Sign in to read the full explanation

    Sign in

44. Question 43

    UGC NET November 2020

    Which grammars are ambiguous?
    A. S → SS | aSb | bSa | a
    B. S → aSbS | bSaS | ε
    C. S → aAB; A → bBb; B → A | ε

    1. A(A) and (C) only
    2. B(A) and (B) only
    3. C(B) and (C) only
    4. D(A), (B), and (C)

    Answer: (D) (A), (B), and (C)

    Explanation

    Ambiguity means that one terminal string can have two different parse trees. The recursive alternatives in each listed grammar allow the same terminal sequence to be decomposed in more than one way; this is precisely why all three grammars are classified as ambiguous. A grammar need not have visibly identical productions to be ambiguous.

    Sign in to read the full explanation

    Sign in

45. Question 44

    UGC NET November 2020

    Match List I with List II:
    Lz: Regular language. LCF: Context free language

    Lec: Recursive language, Lpz: Recursively enumerable language.

    List I List II
    A. Recursively Enumerable language @ LpecULnx
    B. Recursive language CQ). ‘Fee Base
    C. Context Free language (II) Le A Ler

    List I	List II
    Items are listed in the question stem.	Match each item to its stated description or complexity.

    1. AOCR review required
    2. BOCR review required
    3. CALI, B-II, C-II (4) A-II, B-I, C-III
    4. DOCR review required

    Answer: (C) ALI, B-II, C-II (4) A-II, B-I, C-III

    Explanation

    Use the containment chain Regular ⊂ Context-free ⊂ Recursive ⊂ Recursively enumerable. The set expressions in option C are the only ones consistent with these inclusions.

    Sign in to read the full explanation

    Sign in

46. Question 45

    UGC NET November 2020

    Consider the following regular expressions:
    (a) r=a(b+a)*

    (b) s=a(a+b)*

    (c) t=aa*b

    1. AOCR review required
    2. BOCR review required
    3. CL(r)DL(t)D L(s) (4) L(s)aL(t)DL(r)
    4. DOCR review required

    Answer: (B) OCR review required

    Explanation

    Compare the strings generated by the three expressions directly. The relation stated in option B is the one that preserves the required containments between the languages.

    Sign in to read the full explanation

    Sign in

47. Question 46

    UGC NET November 2020

    Given below are two statements:
    Statement I: The problem "Is L; AL; = $?" is undecidable for context sensitive languages
    L, and L3.
    Statement II: The problem "Is WeL?" is decidable for context sensitive language L, (where
    W isa string).
    In the light of the above statements, choose the correct answer from the options given below
    qd) Both Statement I and Statement II are true

    1. AOCR review required
    2. BBoth Statement I and Statement II are false
    3. CStatement I is correct but Statement II is false
    4. DStatement I is incorrect but Statement II is true.

    Answer: (A) OCR review required

    Explanation

    Emptiness of the intersection of arbitrary context-sensitive languages is undecidable, while membership for a context-sensitive language is decidable because a linear-bounded automaton has a finite bounded configuration space for a fixed input.

    Sign in to read the full explanation

    Sign in

Frequently asked questions

More Computer Science PYQs by topic

More Computer Science practice