UGC NET Computer Science Theory of Computation and Compilers Previous Year Questions (PYQs)
Practise 167 Theory of Computation and Compilers questions asked in UGC NET Computer Science from 2018–2026. Questions cover Finite automata, Regular expressions, Context-free grammars, Turing machines, Chomsky hierarchy of languages and Compiler phases and lexical analysis. Every question is shown with its options and the correct answer, free to read.
167 PYQs2018–2026Answers includedFree
Practise Theory of Computation and Compilers as timed sets
Focused 10-question sets with instant scoring, explanations, and weak-area analysis.
Given Pred(x) = x − 1 and T(x, y + 1) = Pred(T(x, y)), with T(x, 0) = x, which operation is a candidate for T?
ASubtraction operation
BAddition operation
CMultiplication operation
DDivision operation
Answer:(A) Subtraction operation
Explanation
The recurrence applies the predecessor operation once for every increment of y. Thus T(x, y) = x − y, which is subtraction; addition would instead require a successor operation.
Arrange these language families from specialization to generalization.
A. All regular languages
B. All Turing-acceptable languages
C. All Turing-decidable languages
D. All context-free languages
AA, B, C, D
BA, C, B, D
CA, D, C, B
DA, D, B, C
Answer:(C) A, D, C, B
Explanation
Every regular language is context-free; every context-free language is decidable; and every decidable language is Turing-acceptable (recursively enumerable). The inclusions therefore grow as A, D, C, B.
AFor a context-free grammar G and string x, membership x ∈ L(G) can be decided in polynomial time.
BIf L is context-free, then its complement is also context-free.
CThe language {aⁿbᵐcᵖ : m, n, p ≥ 0, m ≠ n or m ≠ p} is not deterministic context-free.
DThe class of deterministic context-free languages is closed under intersection.
Answer:(B) If L is context-free, then its complement is also context-free.
Explanation
The supplied source confirms option B as the intended incorrect statement: context-free languages are not closed under complement. The paper designates B as the single answer for this MCQ.
A. L₁ = {aⁿbᵐ | n, m ≥ 0} B. L₂ = {aⁿbᵐ | n = m ≥ 0} C. L₃ = {aⁿbⁿcⁿdⁿeⁿ | n ≥ 1} D. L₄ = {aⁿbᵐcᵐdⁿe² | n, m ≥ 0}
I. Unrestricted II. Context sensitive III. Regular IV. Context free
AA-III, B-I, C-II, D-IV
BA-III, B-IV, C-I, D-II
CA-III, B-II, C-IV, D-I
DA-II, B-III, C-IV, D-I
Answer:(B) A-III, B-IV, C-I, D-II
Explanation
The supplied source annotation designates option B, A-III, B-IV, C-I, D-II, as the intended key. The language definitions are retained exactly as printed so learners can compare the paper's classification convention with the formal language hierarchy.
Which is not part of the general activation record of a procedure?
ALocal data
BGlobal data
CAccess link
DTemporaries
Answer:(B) Global data
Explanation
An activation record stores data associated with one invocation: local variables, temporary values, and links for non-local access. Global data has program-wide lifetime and is not stored in each procedure activation record.
Which option is the minimized DFA equivalent to the DFA shown?
Original DFA and the four proposed minimized automata.
AOption 1
BOption 2
COption 3
DOption 4
Answer:(A) Option 1
Explanation
The accepting state q4 is distinct. The remaining non-accepting states partition into two equivalent behaviours, producing the three-state DFA shown in option 1: an initial state A, state B with a 0 loop, and accepting state C reached on 1.
If L₁ is a regular language and L₂ is a context-free language, which statement is correct?
AAny subset of L₁ ∪ L₂ is context-free
BL₁ ∩ L₂ is context-free
CL₁ / L₂ is regular
DL₁ ∩ L₂ is accepted by a deterministic pushdown automaton
Answer:(B) L₁ ∩ L₂ is context-free
Explanation
Context-free languages are closed under intersection with regular languages. Construct a product of a pushdown automaton for L₂ and a finite automaton for L₁ to recognise L₁ ∩ L₂. CFLs are not closed under arbitrary subsets or intersection with another CFL, and the resulting CFL need not be deterministic.
Which statement may be false for a decision problem X ∈ NP?
AX can be solved in nondeterministic polynomial time
BX can be solved in exponential time
CX can be solved in polynomial space
DX can be solved in deterministic polynomial time
Answer:(D) X can be solved in deterministic polynomial time
Explanation
Membership in NP guarantees a nondeterministic polynomial-time algorithm. Such a computation can be simulated deterministically in exponential time and therefore uses at most polynomial space for a bounded path, but whether every NP problem has a deterministic polynomial-time algorithm is exactly the unresolved P versus NP question.
In S → AB, FIRST(B) contributes + to FOLLOW(A), and because B can derive ε, FOLLOW(S) = {], $} also contributes. In A → CD, FIRST(D) contributes * to FOLLOW(C); D can derive ε, so FOLLOW(A) also contributes +, ], and $. Therefore FOLLOW(A) = {+, ], $} and FOLLOW(C) = {*, +, ], $}.
For the grammar S → AB; B → +AB | ε; A → CD; D → *CD | ε; C → [S] | x, identify the correct statement.
AThe grammar is left recursive
BThe grammar needs left factorization
C[[x*x]+x] is a valid sentence of the grammar
DThe grammar has an SLR(0) parser
Answer:(C) [[x*x]+x] is a valid sentence of the grammar
Explanation
The grammar generates expressions made from x and bracketed S expressions, with D adding repeated multiplication and B adding repeated addition. Thus [[x*x]+x] derives through C → [S], S → AB, and the recursive B/D productions. It is neither left recursive nor left-factored, and “SLR(0)” is not a parser class.
For the grammar S → AB; B → +AB | ε; A → CD; D → *CD | ε; C → [S] | x, how many non-blank LL(1) table entries occur in the B and D rows?
AB = 3; D = 4
BB = 6; D = 5
CB = 2; D = 3
DB = 1; D = 2
Answer:(A) B = 3; D = 4
Explanation
For B → +AB, FIRST is {+}, so M[B,+] is one non-blank entry. Because B → ε, put that production under every symbol in FOLLOW(B) = {], $}, yielding two more entries and B = 3. Likewise D → CD gives M[D,], while D → ε is entered for FOLLOW(D) = {+, ], $}; that is one plus three, so D = 4.
For the augmented grammar S′ → S; S → AB; B → +AB | ε; A → CD; D → *CD | ε; C → [S] | x, how many productions are in the I₁ state of the canonical LR(0) set?
A1
B2
C4
D6
Answer:(A) 1
Explanation
I₀ contains S′ → ·S together with the closure productions for S, A, and C. Taking GOTO(I₀, S) produces I₁ = {S′ → S·}; the dot is at the end, so no closure expansion is added. Thus I₁ has exactly one item/production.
Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R
Assertion (A): If L is regular, then its compliment L' is necessarily regular.
Reason (R): Complement of a language can be obtained by swapping final and non-final states in a DFA.
ABoth A and R are correct and R is the correct explanation of A
BBoth A and R are correct but R is NOT the correct explanation of A
CA is correct but R is not correct
DA is not correct but R is correct
Answer:(A) Both A and R are correct and R is the correct explanation of A
Explanation
Regular languages are closed under complement. Given a DFA for L, swapping every accepting state to non-accepting and vice versa produces a DFA that accepts exactly the strings L rejects, which is the complement of L. Since a DFA always exists for any regular language, this complement is itself regular, so Assertion A holds.
Reason R states this construction correctly and restricts it to a DFA, where the swap works precisely because the DFA is deterministic and total, so every string reaches exactly one state. This construction is the actual reason A is true, so R correctly explains A.
A phase of a compiler which produces the symbol table is
ASyntax analysis
BSemantic analysis
CTarget code generation
DCode optimization
Answer:(A) Syntax analysis
Explanation
Symbol table entries for identifiers and declarations are created as the parser recognizes declaration constructs while building the parse tree, so syntax analysis is the phase that produces the symbol table.
A. Syntax analysis — correct. The parser creates symbol table entries while recognizing declarations in the grammar.
B. Semantic analysis — this phase uses and updates existing symbol table entries with type and scope information, it does not originate the table.
C. Target code generation — this phase consumes finalized symbol table information to generate machine code, long after the table already exists.
D. Code optimization — this phase transforms intermediate code for efficiency and does not create symbol table entries.
Which of the following languages cannot be accepted by a pushdown automaton?
A. L = { aⁿbⁿcⁿ : n ≥ 0 }
B. L = { aᵖ : p is Prime }
C. L = { wcwᴿ : w ∈ (a, b)* }
D. L = { w ∈ (a, b)* : nₐ(w) = n_b(w) }
E. L = { aⁿbᵐc⁽ⁿ⁺ᵐ⁾ : n ≥ 0, m ≥ 0 }
AA, C & D Only
BB, D & E Only
CA & B Only
DC & D Only
Answer:(C) A & B Only
Explanation
A pushdown automaton has only one stack, so it can enforce at most one counting relationship between symbols at a time, not two independent relationships simultaneously.
A. Cannot be accepted. Matching aⁿbⁿcⁿ needs two independent equalities, n = (number of b's) and n = (number of c's), and a single stack cannot verify both at once, so this language is not context-free.
B. Cannot be accepted. This is a unary language, and every context-free language over a one-letter alphabet is actually regular, so it is context-free only if its exponents form an eventually periodic set. Prime numbers are not eventually periodic, so this language is neither regular nor context-free.
C. Can be accepted. A PDA pushes w onto the stack while reading it, then pops and matches symbols against wᴿ after seeing c, the standard construction for such center-marked languages.
D. Can be accepted. The stack tracks the running difference between the counts of a's and b's, pushing on one symbol and popping on the other, a classic PDA construction for equal-count languages.
E. Can be accepted. A PDA pushes once for each a and once for each b onto the same stack, then pops once per c, so it accepts exactly when the number of c's equals n + m.
Only A and B describe languages a PDA cannot accept, so A & B Only is correct.
Match List-I (Grammar types) with List-II (Production forms).
List-I (Grammar)
List-II (All productions are of the form)
A. Regular Grammar
I. A → aX, where a ∈ T and X ∈ V*
B. Unrestricted Grammar
II. A → xB, A → x or A → Bx, A → x where A, B ∈ V and x ∈ T*
C. Chomsky Normal Form
III. x → y, where x ∈ (V ∪ T)+ and y ∈ (V ∪ T)*
D. Greibach Normal Form
IV. A → BC or A → a, where A, B, C are in V and a is in T
AA-II, B-III, C-I, D-IV
BA-I, B-III, C-II, D-IV
CA-II, B-III, C-IV, D-I
DA-II, B-IV, C-I, D-III
Answer:(C) A-II, B-III, C-IV, D-I
Explanation
Each grammar type has a distinct restriction on the shape of its productions.
A-II — Regular grammar productions are right-linear (A → xB or A → x) or left-linear (A → Bx or A → x), with x a string of terminals, matching item II.
B-III — Unrestricted grammar places no shape restriction beyond x containing at least one variable, matching the most general form x → y in item III.
C-IV — Chomsky Normal Form restricts every production to exactly two variables (A → BC) or a single terminal (A → a), matching item IV.
D-I — Greibach Normal Form requires every production to start with exactly one terminal followed only by variables (A → aX), matching item I.
A-II, B-III, C-IV, D-I is therefore the correct match.
Arrange the following tasks of a lexical analyzer in the correct sequence.
A. Token Generation.
B. Removal of comments/White sphere.
C. Buffering and reading source characters.
D. Return token stream to parser.
AA, B, C, D
BB, A, C, D
CC, B, A, D
DB, A, D, C
Answer:(C) C, B, A, D
Explanation
A lexical analyzer first buffers and reads the raw source characters, strips out comments and white space that carry no lexical meaning, groups the remaining characters into tokens, and then passes the resulting token stream on to the parser.
C-B-A-D — Buffering and reading source characters, Removal of comments/white space, Token Generation, Return token stream to parser — is the correct sequence.
If r₁ and r₂ are regular expressions, then which of the following are correct?
A. L(r₁ + r₂) = L(r₁) ∪ L(r₂)
B. L(r₁ · r₂) = L(r₁)L(r₂)
C. L((r₁)) = L(r₁)
D. L(r₁*) = (L(r₁))*
AA & B Only
BB, C & D Only
CA, C & D Only
DA, B, C & D
Answer:(D) A, B, C & D
Explanation
Each statement is a direct restatement of how regular expression operators map to language operations.
A. The union operator + between two regular expressions produces the union of the two languages, so L(r₁ + r₂) = L(r₁) ∪ L(r₂) holds by definition.
B. Concatenating two regular expressions produces the concatenation of their languages, so L(r₁ · r₂) = L(r₁)L(r₂) holds by definition.
C. Parentheses only group a regular expression for precedence and do not change what it denotes, so L((r₁)) = L(r₁) holds trivially.
D. The Kleene star operator on a regular expression produces the Kleene closure of its language, so L(r₁*) = (L(r₁))* holds by definition.
All four statements correctly describe how regular expression syntax corresponds to language operations, so all of A, B, C and D are correct.
What is the space complexity of the CYK algorithm for the P table, where n is the number of words in the sentence and m is the number of non-terminal symbols in the grammar?
AO(n³)
BO(nm²)
CO(n²m)
DO(n²m²)
Answer:(C) O(n²m)
Explanation
The CYK algorithm fills a triangular table P where each cell corresponds to a span (i, j) of the input, and there are O(n²) such spans for a sentence of n words.
Each cell must record which of the m nonterminal symbols can derive that span, which needs O(m) space per cell in the worst case.
Multiplying the number of cells by the storage per cell gives total space O(n²) × O(m) = O(n²m).
Assertion (A): L = {aⁿbⁿcⁿ : n ≥ 0} is accepted by a linear bounded automaton.
Reason (R): Linear bounded automata recognize exactly the class of context-sensitive languages.
ABoth A and R are correct and R is the correct explanation of A
BBoth A and R are correct but R is NOT the correct explanation of A
CA is correct but R is not correct
DA is not correct but R is correct
Answer:(A) Both A and R are correct and R is the correct explanation of A
Explanation
The language L = {aⁿbⁿcⁿ : n ≥ 0} is a classic example of a context-sensitive language that is not context-free.
Linear bounded automata (LBAs) are exactly the automata that recognize the class of context-sensitive languages, so any context-sensitive language, including this one, is accepted by some LBA.
Since Assertion A is true and Reason R states the precise theorem that explains why A holds, R correctly explains A.
Arrange the following steps in the order of execution while proving that a language is non-regular using the Pumping Lemma.
A. Split the string into xyz satisfying the pumping lemma conditions
B. Assume the language is regular
C. Choose a string of length greater than or equal to the pumping length
D. Show a contradiction when pumping y
AB, C, D, A
BC, D, A, B
CB, C, A, D
DA, B, C, D
Answer:(C) B, C, A, D
Explanation
Proving a language is not regular with the pumping lemma follows a fixed logical sequence, since each step depends on the one before it.
First, assume the language is regular (B), since the proof works by contradiction against this assumption.
Next, choose a string in the language of length at least the pumping length guaranteed by the lemma (C).
Then split that string into parts x, y, z satisfying the pumping lemma's length and repetition conditions (A).
Finally, show that pumping the y portion produces a string that is not in the language, contradicting the assumption (D).
Which is the best description of the language accepted by the DFA?
DFA over the alphabet {a, b, c}.
AL = (a* + b* + c*)+
BL = (a + b + c)(abc)+(a + b + c)
CThe set of strings that start with a, b, or c and end with c
DThe set of strings having an even count, including zero, of the substring abc
Answer:(D) The set of strings having an even count, including zero, of the substring abc
Explanation
The automaton's states track progress through a possible abc and whether a completed occurrence has changed the parity. The initial accepting state represents zero completed occurrences; completing abc moves to the opposite-parity group, and completing another returns to the accepting group. Thus it accepts exactly strings with an even number of abc occurrences.
A valid NFA must preserve the DFA's accepted language while allowing nondeterministic state choices. Comparing the transition alternatives and accepting states shows that diagram 4 retains the required accepting paths without accepting a string that the DFA rejects; the other diagrams alter an accepting state or omit a required transition alternative.
Arrange LL(0), LR(0), SLR, LALR(1), and LR(1) parsers from least to greatest grammar-handling power.
ALL(0) → LR(0) → SLR → LR(1) → LALR(1)
BSLR → LR(0) → LL(0) → LR(1) → LALR(1)
CLL(0) → LR(0) → SLR → LALR(1) → LR(1)
DLR(0) → LL(0) → SLR → LR(1) → LALR(1)
Answer:(C) LL(0) → LR(0) → SLR → LALR(1) → LR(1)
Explanation
LL(0) has no lookahead and is most restricted. LR(0) adds bottom-up item sets, SLR uses FOLLOW sets to reduce conflicts, LALR(1) merges compatible LR(1) states, and canonical LR(1) retains the most lookahead information. Hence C gives the increasing order.
Editorially repaired version of an ambiguous NTA item. Which grammars are context-free but not regular?
Grammar
Productions
A
S → Ab; aS → aA; A → a
B
S → Ab; A → Sa; A → a
C
S → AS; S → aA; A → a
D
S → Ab; S → aA; A → a
E
S → Sb; A → Aa; A → ε
AA and B only
BC and D only
CC only
DA, B, D, and E only
Answer:(C) C only
Explanation
A context-free grammar must have one nonterminal on the left of every production. A is not context-free because it has aS → aA. B, D, and E are regular because their productions are consistently linear. C is context-free but not regular because S → AS has two nonterminals on its right side. Thus only C qualifies. The source's answer set was repaired to include that result explicitly.
Match Types 3, 2, 1, and 0 grammars to their production restrictions.
List I
List II
A. Type 3 Grammar
I. V → (V ∪ Σ)*
B. Type 2 Grammar
II. λVβ → λ(V ∪ Σ)*β, where (λ, β) ∈ (V ∪ Σ)*
C. Type 1 Grammar
III. (V ∪ Σ)* → (V ∪ Σ)*
D. Type 0 Grammar
IV. V → VΣ | Σ
AA-II, B-III, C-IV, D-I
BA-III, B-I, C-IV, D-II
CA-IV, B-I, C-II, D-III
DA-III, B-II, C-I, D-IV
Answer:(C) A-IV, B-I, C-II, D-III
Explanation
Type 3 grammars use the regular production form V → VΣ or Σ. Type 2 allows a single variable on the left, V → (V ∪ Σ)*. Type 1 uses noncontracting contextual productions λVβ → λ(V ∪ Σ)β, and Type 0 has unrestricted productions over (V ∪ Σ). This gives A-IV, B-I, C-II, D-III.
Which high-level program corresponds to the displayed three-address code?
Three-address code and its four high-level-code alternatives.
ASource code option 1
BSource code option 2
CSource code option 3
Dinit = x/(y+2); limit = 10; while (i > j && num > b) { num = limit-1; b = y+2; i = i-num; } j = i-num; k = j+b;
Answer:(D) init = x/(y+2); limit = 10; while (i > j && num > b) { num = limit-1; b = y+2; i = i-num; } j = i-num; k = j+b;
Explanation
The two conditional jumps send execution to the loop body only when both i > j and num > b hold. The loop body recomputes num, b, and i, then jumps back to the first condition; on either failed condition it computes j and k. That control flow is the while form in option D.
100: t1 = y + 2
101: initial = x / t1
102: limit = 10
103: if i > j goto 105
104: goto 111
105: if num > b goto 107
106: goto 111
107: num = limit - 1
108: b = y + 2
109: i = i - num
110: goto 103
111: j = i - num
112: k = j + b
A100, 102, 103, 104, 105, 107, 110
B100, 103, 105, 107, 111, 112
C100, 103, 105, 106, 107, 111
D100, 103, 104, 105, 106, 107, 111
Answer:(D) 100, 103, 104, 105, 106, 107, 111
Explanation
The first statement is a leader. Every jump target—103, 105, 107, and 111—is a leader, and each statement immediately following a conditional jump is also a leader: 104 and 106. This gives 100, 103, 104, 105, 106, 107, and 111.
Which displayed flow graph is correct for the given three-address code?
Four adjacency-matrix flow-graph alternatives for the three-address code.
AAdjacency-matrix option 1
BAdjacency-matrix option 2
CAdjacency-matrix option 3
DAdjacency-matrix option 4
Answer:(A) Adjacency-matrix option 1
Explanation
Partitioning at the leaders yields blocks for initialization, both tests and fall-throughs, the loop body, and the exit. The graph must have the two test branches, the loop-back edge from the body to the first test, and both failed-condition edges to the exit; only option A has that structure.
In the flow graph for the given three-address code, which blocks are dominated by Block 3 and Block 5?
ABlock 3: 3; Block 5: 5
BBlock 3: 3, 4, 5, 6; Block 5: 5, 6
CBlock 3: 3, 7; Block 5: 5, 7
DBlock 3: 3, 4, 7; Block 5: 5, 6, 7
Answer:(A) Block 3: 3; Block 5: 5
Explanation
A block dominates another only when every path from the entry to that block passes through it. The branch structure allows the exit to be reached through paths that bypass each of the named decision blocks, so neither dominates another distinct block. Each block dominates itself, giving option A.
Editorially repaired version of an NTA-dropped item. Consider this three-address code. Assume y is not reassigned between lines 100 and 108. Which single change is a semantics-preserving common-subexpression elimination?
100: t1 = y + 2
101: initial = x / t1
102: limit = 10
103: if i > j goto 105
104: goto 111
105: if num > b goto 107
106: goto 111
107: num = limit - 1
108: b = y + 2
109: i = i - num
110: goto 103
111: j = i - num
112: k = j + b
AReplace only line 108 with b = t1.
BMove num = limit - 1 before the test at line 105.
CReplace lines 111–112 with k = i + b.
DReplace line 109 with i = i - limit - 1.
Answer:(A) Replace only line 108 with b = t1.
Explanation
Line 100 already computes y + 2 into t1, and the stated assumption ensures that value is still valid at line 108. Replacing b = y + 2 with b = t1 therefore eliminates a repeated computation without changing the program. Moving the assignment to num changes the value tested at line 105; k = i + b omits the subtraction of num; and i - limit - 1 is not equal to i - (limit - 1).
The kinds of symbols for basic syntactic elements of first-order logic are:
A. Constant
B. Domain
C. Predicate
D. Temporal
E. Function
AB and D only
BA, B and C only
CA, C and E only
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.
Which statement is true about the pumping lemma for regular languages?
AIt applies to all regular languages
BIt applies only to infinite regular languages
CIt applies to all context-free languages
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.
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
AA, C, B, D, E
BB, C, D, A, E
CC, D, A, B, E
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.
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
AA-III, B-II, C-IV, D-I
BA-II, B-IV, C-I, D-III
CA-II, B-III, C-I, D-IV
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.
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
AA and B only
BB only
CC only
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.
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.
AA and C only
BB and D only
CA, B and C only
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.
Which language is represented by the displayed Turing-machine transition function?
A{aⁿbⁿ | n ≥ 0}
B{abⁿ | n ≥ 1}
C{ab* | n > 0}
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.
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
AA-I, B-II, C-III, D-IV
BA-II, B-I, C-III, D-IV
CA-III, B-II, C-IV, D-I
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.
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.
For the automaton described in the accompanying comprehension passage, which displayed diagram represents the minimum-state DFA?
DFA options 1-4 for Question 141
ADFA diagram 1
BDFA diagram 2
CDFA diagram 3
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.
For the automaton in the preceding comprehension passage, which displayed diagram is correct?
DFA options 1-4 for Question 142
ADFA diagram 1
BDFA diagram 2
CDFA diagram 3
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.
For the preceding automaton passage, which displayed DFA represents the language accepted by the machine?
DFA options 1-4 for Question 143
ADFA diagram 1
BDFA diagram 2
CDFA diagram 3
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.
For the automaton described in the comprehension passage, which regular expression represents its accepted language?
A(a+b)*aab
Baba(a+b)*
Cb(a+b)*b(a+b)a(a+b)
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.
For the automaton described in the comprehension passage, which grammar represents the language accepted by the machine?
AS → AabbB, A → aA | ε, B → bB | ε
BS → abbA, A → aA | ε | bA
CS → AabbA, A → aA | bA | ε
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.
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?
A{x,y}
B{y,z}
C{z,x}
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.
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.
A(A) and (B) Only
B(B) and (C) Only
C(C) and (D) Only
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.
If L₁ and L₂ are context free languages, which one of the following is true about L₁ ∩ L₂?
AL1 L2 is context free.
BL1 L2 is Regular
CL1 L2 is Recursive Enumerable
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.
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
A(A), (B), (C) Only
B(B), (C), (D) Only
C(A), (C), (D) Only
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.
(III) Object-oriented programming language for web applications.
(D) JAVA
(IV) Used for data storage and transport.
A(A)-(I), (B)-(III), (C)-(II), (D)-(IV)
B(A)-(II), (B)-(III), (C)-(IV), (D)-(I)
C(A)-(II), (B)-(I), (C)-(IV), (D)-(III)
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.
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
A(C), (A), (B), (D), (E)
B(C), (B), (A), (D), (E)
C(C), (D), (A), (B), (E)
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.
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}
A(A) and (B) only
B(B) and (C) only
C(C) and (D) only
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.
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
A(A), (B), (C), (D), (E)
B(A), (C), (B), (D), (E)
C(A), (D), (B), (C), (E)
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.
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
A(C), (A), (B), (D)
B(C), (A), (D), (B)
C(A), (C), (B), (D)
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.
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}
A(A) and (B) only
B(B) and (C) only
C(C) and (D) only
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.
Let L={ab, aa, baa}. Which of the following strings are not in L*.
Aabaabaaabaa
Baaaabaaaa
Cbaaaaabaaaab
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.
Let A={a, b} and L=A*. Let x={a"b", n>0}. The languages L U X and X are respectively :
ANot regular, Regular
BRegular, Regular
CRegular, Not regular
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.
Which of the following symbol table implementation is best suited if access time is to be minimum ?
A_ Linear list
BSearch tree
CHash Table
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.
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 ?
An,E+nandE+nxn
Bn,E+nand E+Exn
Cn,n+nandn+nxn
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.
One of the purposes of using intermediate code in compilers is to :
Amake parsing and semantic analysis simpler
Bimprove error recovery and error reporting
Cincrease the chances of reusing the machine independent code optimizer in other compilers
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.
The sum of minimum and maximum number of final states for a Deterministic Finite Automata (DFA) having 'P" state is equal to : () Pp
Ap
Bp-1
Cp+1
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.
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 :
A(A) and (B) Only
B(A), (B) and (D) Only
C(B) and (C) Only
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.
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 :
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 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 :
AC → A → D → B → E
BB → C → A → D → E
CC → B → D → A → E
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.
Which of the following parser is most powerful parser?
AOperator precedence
BSLR
CCanonical LR
DLALR
Answer:(C) Canonical LR
Explanation
Among shift-reduce parsers, the LR parser family forms a strict power hierarchy. Canonical LR (LR(1)) can handle every grammar that SLR and LALR can, plus more, because it keeps a distinct lookahead set for every individual state-item pair instead of merging states. SLR and LALR are more restrictive since they merge states to save memory, which can introduce parsing conflicts that Canonical LR avoids. Operator precedence parsing is weaker still, working only for a narrow class of expression grammars. So Canonical LR is the most powerful parser of the four.
BL = {aⁿ bᵏ cⁿ⁺ᵏ : n ≥ 0, k ≥ 0} is regular language.
CL = {aⁿ bʲ : n = j²} is not context free language
DFor every context sensitive language L not including λ, there exists some linear bounded automata M such that L ≠ L(M).
Answer:(C) L = {aⁿ bʲ : n = j²} is not context free language
Explanation
Check each statement against standard computability and formal language results.
A. Ackermann's function is primitive recursive. False. Ackermann's function is the textbook example of a total computable function that grows faster than any primitive recursive function, so it is not primitive recursive.
B. L = {aⁿ bᵏ cⁿ⁺ᵏ} is regular. False. This language needs to compare the combined count of a's and b's against the count of c's, which requires unbounded counting that a finite automaton cannot perform. It is context-free, since a pushdown automaton can track the running count using its stack, but it is not regular.
C. L = {aⁿ bʲ : n = j²} is not context free. True. This language requires the number of b's to equal the square of the number of a's, and the context-free pumping lemma shows no pushdown automaton can enforce a quadratic relationship between symbol counts.
D. For every context sensitive language L not including λ, there exists a linear bounded automaton M such that L ≠ L(M). False as stated. The actual theorem runs the opposite way: every context-sensitive language not containing the empty string equals the language accepted by some linear bounded automaton, meaning L = L(M), not L ≠ L(M).
Consider the finite automaton F1 shown, which accepts a language L over its input alphabet. C is the start state and E (double circle) is the only accepting state. The transitions are: C to S, S to E, and C to E directly (three forward edges), together with S back to C and E back to S (two backward edges). Let F2 be the finite automaton obtained by reversal of F1 (reverse every transition and swap the roles of the start and accepting states). Then which of the following is correct?
AL(F1) ≠ L(F2)
BL(F1) = L(F2)
CL(F1) ≤ L(F2)
DL(F1) ≥ L(F2)
Answer:(B) L(F1) = L(F2)
Explanation
Reversing an automaton means reversing every transition's direction and swapping the roles of the start and accepting states. F1 has five directed edges: C→S, S→E, C→E, S→C, and E→S.
Reversing each edge gives: S→C, E→S, E→C, C→S, and S→E. Four of these five reversed edges (S→C, E→S, C→S, S→E) already exist in F1's own edge set. Only one edge changes: F1's direct C→E shortcut becomes E→C in the reversal.
The diagram carries no distinct input-symbol labels on its transitions, so each edge represents a move on the same single input symbol. A finite automaton whose transitions are all labelled with one repeated symbol accepts a language made only of strings like a, aa, aaa, and so on, a language fully determined by string length rather than symbol pattern. Every string built from one repeated symbol reads the same forwards and backwards, so it is automatically its own reverse.
Because reversing an automaton produces the reverse of its language, and a single-symbol language is always equal to its own reverse, L(F2) must equal L(F1) here regardless of the one edge whose direction flips. The near-total edge overlap between F1 and its reversal reinforces the same conclusion structurally, but the single-symbol argument holds even without relying on that overlap.
A. L(F1) ≠ L(F2) — would hold for a language over a multi-symbol alphabet that is not itself reversal-closed, but not here.
B. L(F1) = L(F2) — correct. A single-symbol automaton's language is always closed under reversal.
C. L(F1) ≤ L(F2) — not a valid set-theoretic comparison between two languages.
D. L(F1) ≥ L(F2) — not a valid set-theoretic comparison between two languages.
The maximum yield length of the following CNF CFG is
S → AB
A → CD
B → e
C → a
D → b
A8
B7
C4
D5
Answer:(D) 5
Explanation
This grammar is in Chomsky Normal Form because every rule is either A → BC (two nonterminals) or A → a (one terminal): S → AB, A → CD, B → e, C → a, D → b.
Since every nonterminal has exactly one production, there is only one possible derivation:
S ⇒ AB ⇒ CDB ⇒ aDB ⇒ abB ⇒ abe
The derived string "abe" has length n = 3. A standard theorem for CNF grammars states that any derivation of a string of length n takes exactly 2n − 1 production steps. Here 2(3) − 1 = 5, which matches the derivation above (S→AB, A→CD, C→a, D→b, B→e is 5 steps).
A. 8 — this is the total node count of the full parse tree (5 nonterminal nodes + 3 terminal leaves), not the derivation length.
B. 7 — this is the edge count of the parse tree, one less than the total node count.
C. 4 — does not correspond to either the string length or the standard 2n − 1 step count.
D. 5 — correct. It matches 2n − 1 with n = 3, the number of production steps needed to derive the unique string "abe".
A. A context free language is generated by LR(0) grammar if and only if it is accepted by a deterministic pushdown automata and has prefix property
B. If M1 is the single tape TM simulating multitape TM M, then time taken by M1 to simulate n moves is O(n²)
C. Push down automata behaves like a Turing machine when it has one auxiliary memory.
D. L = {aⁿbⁿcⁿ : n ≥ 1} is not context free but context sensitive.
AA, B and C only
BA, B only
CD only
DB, C only
Answer:(A) A, B and C only
Explanation
Each statement needs its own check against standard automata and complexity theory, since the option set only offers partial combinations of A-D.
A — true. The equivalence between LR(0) grammars, deterministic PDA acceptance, and the prefix property is a standard result in parsing theory.
B — true. The well-established theorem is that a single-tape Turing machine simulating n moves of a multitape machine takes O(n²) time, exactly the bound this statement gives.
C — genuinely ambiguous on its own wording. One auxiliary memory can be read two ways. Read literally as the PDA's own single stack, an ordinary PDA already has exactly that one auxiliary memory and is strictly weaker than a Turing machine, so C would be false. Read as textbook shorthand for one auxiliary memory in addition to the PDA's stack, giving it two unbounded stores in total, C matches the standard theorem that a PDA augmented with a second stack (or equivalent extra unbounded memory) becomes Turing-equivalent, so C would be true under this common convention.
D — true. {aⁿbⁿcⁿ : n ≥ 1} fails the context-free pumping lemma but is decidable by a linear bounded automaton, so it is context-sensitive but not context-free.
Taking C under its standard-textbook reading, the true statements are A, B, C, and D, a combination no option lists. Option 1 (A, B and C only) is the closest available match among the four given choices and is the answer this item is built around, even though the item cannot be fully reconciled with any option under the strictest possible reading of C.
A. The set of Turing machine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is decidable
B. The language of codes for TM's M that when started with blank tape, eventually write a 1 somewhere on the tape is undecidable
C. The language accepted by a TM M is L(M) is always recursive
D. Post's correspondence problem is undecidable
AA, B and C only
BB, C and D only
CA and C only
DB and D only
Answer:(D) B and D only
Explanation
Each statement is a known decidability result about Turing machines.
A claims decidability for {⟨M⟩ : L(M) ⊇ set of palindromes}. This asks whether an arbitrary property of the language a machine recognizes is decidable. By Rice's theorem, every non-trivial semantic property of the language recognized by a Turing machine is undecidable, and "accepts at least all palindromes" is such a property, so this is undecidable. Statement A is false.
B claims undecidability for {⟨M⟩ : M started on a blank tape eventually writes a 1 somewhere}. This is a non-trivial property of M's behavior and is undecidable by Rice's theorem. Statement B is true.
C claims L(M) is always recursive. This is false — L(M) is only guaranteed to be recursively enumerable, since M may run forever without accepting or rejecting on some inputs, in which case L(M) need not be recursive.
D claims Post's Correspondence Problem is undecidable. This is a classical, well-established undecidability result. Statement D is true.
Only B and D are true.
A. A, B and C only — wrongly includes false statement A and false statement C.
B. B, C and D only — wrongly includes false statement C.
C. A and C only — both statements in this option are false.
D. B and D only — correct. Both B and D are genuine undecidability results, while A and C are false.
A. If some NP-complete problem P is in ℙ (P class) then P = NP
B. TSP is in ℕℙ (NP)
C. SAT is in ℕℙ (NP)
D. Hamilton circuit problem is not NP-complete
AA, B and C only
BB, C and D only
CC, D and A only
DD, A and B only
Answer:(A) A, B and C only
Explanation
Each statement is a standard complexity-theory fact.
A: if any NP-complete problem is shown to be solvable in polynomial time (in P), then every NP problem reduces to it in polynomial time and is therefore also solvable in polynomial time, forcing P = NP. This is a foundational, true statement.
B: the decision version of the Travelling Salesman Problem is in NP, since a proposed tour's total cost can be verified in polynomial time. True.
C: SAT (Boolean satisfiability) is in NP, since a satisfying assignment can be verified in polynomial time — it is also the original Cook-Levin NP-complete problem. True.
D: the Hamiltonian circuit problem is one of Karp's original NP-complete problems, so it is NP-complete. Statement D, which claims it is not NP-complete, is false.
A, B, and C are true, while D is false.
A. A, B and C only — correct, matches the three true statements identified above.
B. B, C and D only — wrongly includes false statement D.
C. C, D and A only — wrongly includes false statement D.
D. D, A and B only — wrongly includes false statement D.
Which phase of a compiler checks the grammar of the programming language?
ACode optimization
BSemantic analysis
CCode generators
DSyntax analysis
Answer:(D) Syntax analysis
Explanation
Syntax analysis is the compiler phase that checks whether the sequence of tokens produced by lexical analysis conforms to the language's grammar, building a parse tree from the grammar's production rules.
A. Code optimization — wrong phase. It improves already-generated intermediate code and does not check grammar.
B. Semantic analysis — wrong phase. It checks meaning-level rules such as type compatibility, after the grammar has already been validated.
C. Code generators — wrong phase. Code generation produces target-machine instructions from validated, optimized intermediate code.
D. Syntax analysis — correct. It is the parsing phase that validates grammatical structure.
Consider the following language over the alphabet {a, b, c}:
L = {w ∈ {a, b, c}* : n_a(w) + n_b(w) = n_c(w)}
Which of the following best describes L?
AContext free but not linear
BNot context free
CContext free and linear
DLinear
Answer:(A) Context free but not linear
Explanation
The language L requires that the combined count of a's and b's equal the count of c's, with no restriction on the order in which the symbols appear.
Treating every a or b as one symbol type and every c as another, L is equivalent to the classic language of equal counts over a two-letter alphabet, which is generated by the context-free grammar S → aSc | cSa | bSc | cSb | SS | ε. This grammar produces every string satisfying the count condition, so L is context-free.
L is not linear, because some valid strings cannot be produced by simple nested matching alone. For example, "acca" satisfies the count condition (two a's, two c's), but its first and last symbols are both a, so no single nesting production of the form aSc or cSa can generate it directly. It can only be built by concatenating two independently balanced pieces, "ac" and "ca", using the SS rule. A linear grammar allows at most one nonterminal per production and cannot express this concatenation of two independently balanced substrings, so L needs a non-linear grammar.
Because L is context-free but requires concatenation of independently generated substrings, the correct classification is context-free but not linear.
The compiler for a high level language that runs on one machine and produces code for a different target machine is called a
ACross compiler
BMultipass compiler
COptimizing Compiler
DOne pass Compiler
Answer:(A) Cross compiler
Explanation
A cross compiler runs on one machine, the host, but generates executable code for a different target machine, which is exactly the relationship described in the question.
A. Cross compiler — correct. Defined by the host-target relationship, it compiles on one architecture for another.
B. Multipass compiler — wrong. This is defined by how many passes it makes over the source code, not by host-target machine differences.
C. Optimizing Compiler — wrong. This focuses on improving generated code's efficiency, unrelated to target machine.
D. One pass Compiler — wrong. This processes source code in a single pass, again unrelated to host-target machine differences.
Statement I: If f and g are two functions and f = O(g) but g is not o(f), we say that the growth rate of g is smaller than that of f
Statement II: The class of all decision problems decided by a Turing Machine in exponential time, that is O(2^k) where k is a constant, is called EXP
Which one of the following is correct in the light of the above statements?
ABoth Statement I and Statement II are correct
BBoth Statement I and Statement II are incorrect
CStatement I is correct but Statement II is incorrect
DStatement I is incorrect but Statement II is correct
Answer:(D) Statement I is incorrect but Statement II is correct
Explanation
Statement I is incorrect. f = O(g) only says f does not grow faster than g. Adding that g is not o(f) rules out g being strictly slower than f, and together these two facts mean f and g grow at the same rate, f = Θ(g), not that g grows slower than f. For example, f(n) = g(n) = n satisfies f = O(g) and g is not o(f), yet the two functions have identical growth, contradicting the statement's claim that g's growth rate is smaller.
Statement II is correct. A decision problem is in the complexity class EXP (EXPTIME) exactly when some deterministic Turing machine decides it in exponential time, bounded by 2 raised to a polynomial in the input size for some constant exponent. This is the standard definition of the exponential-time class.
Since Statement I is incorrect and Statement II is correct, the matching option is the one stating exactly that.
The transition function 'δ' in multi-tape Turing machine is defined as:
Aδ: 2^Q × Γᵏ → 2^Q × Γᵏ × {L, R, S}ᵏ
Bδ: Q × Q × Γᵏ → Q × Q × Γᵏ × {L, R, S}ᵏ
Cδ: Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ
Dδ: Q × Γᵏ × 2^Q → Q × Γᵏ × 2^Q × {L, R, S}ᵏ
Answer:(C) δ: Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ
Explanation
A k-tape Turing machine reads one symbol from each of its k tapes at once, so its transition function must take the current state and a k-tuple of tape symbols as input.
The output is the next state, the k symbols to write, and a movement direction for each of the k heads, giving δ: Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ.
The power-set forms in options A and D describe nondeterministic machines, not the standard deterministic multi-tape definition, so they do not fit here.
In Pumping Lemma for regular languages, to say a language is satisfying pumping lemma, what is the minimum length of 'y' if you consider the string as 'xyz'?
An
B2
C1
D0
Answer:(C) 1
Explanation
The pumping lemma requires the middle segment y to be pumpable, meaning it must be repeatable any number of times, including zero, while the resulting string stays in the language.
A segment of length 0 cannot be meaningfully pumped because repeating an empty string never changes anything, so the lemma's standard statement fixes |y| ≥ 1, which makes 1 the minimum required length.
An LR item marks how much of a production's right-hand side has already been seen with a dot, so for a normal production the dot sits between recognized and unrecognized symbols.
Because A → ε has an empty right-hand side, there are no symbols on either side of the dot to place it between, so the standard convention writes the single resulting item as A → • with the dot alone, omitting the ε symbol entirely rather than writing it out before or after the dot.
In the ε-NFA, M = ({q0, q1, q2, q3}, {a}, δ, q0, {q3}), where 'δ' is given by q0 moving to q1 on ε, q1 moving to q2 on ε, and q2 moving to both q2 and q3 on 'a', what is the minimum length of string to reach the final state?
State
ε
a
q0
{q1}
{}
q1
{q2}
{}
q2
{}
{q2,q3}
q3
{}
{}
Transition table for the ε-NFA
A0
B1
C2
D3
Answer:(B) 1
Explanation
Trace the epsilon-closure of the start state first, because epsilon moves consume no input.
From q0, the epsilon-closure reaches q1 and then q2 without consuming any symbol. The only way to reach the accepting state q3 is the transition from q2 on input 'a', so at least one 'a' is required.
A single 'a' takes the machine from q0, through the epsilon-closure to q2, then directly to q3, so the minimum string length to reach the final state is 1.
Circuit satisfiability problem: Given a Boolean combinational circuit composed of AND, OR and NOT gates, is it satisfiable? A one output Boolean combinatorial circuit is satisfiable means for the given inputs the output will be 1.
A. The circuit satisfiability problem belongs to class NP
B. The circuit satisfiability problem is at least as hard as any language in NP
C. The circuit satisfiability is NP-Complete
D. The size of the circuit is O(K²+1)
E. If P≠NP, this situation would contradict the NP-Completeness of the problem.
Choose the correct answer from the options given below:
AA, C, D Only
BB, D, E Only
CA, B, C Only
DB, C, D Only
Answer:(C) A, B, C Only
Explanation
Circuit satisfiability was the first problem the Cook-Levin theorem proved NP-complete, so its standard properties follow directly from that theorem.
A. Belongs to class NP — true, a satisfying input assignment can be verified in polynomial time by simulating the circuit.
B. At least as hard as any language in NP — true, this is exactly the definition of NP-hardness, and Cook-Levin proves every NP problem reduces to it.
C. Is NP-Complete — true, being both in NP and NP-hard is precisely what NP-Complete means.
D. Circuit size is O(K²+1) — this is not a general property of circuit satisfiability, so it does not belong here.
E. If P≠NP, this would contradict NP-Completeness — false. P≠NP is entirely consistent with circuit satisfiability being NP-complete, it does not contradict it.
Which of the following is (are) correct about the regular expression aabbccdd
A. The language represented by the regular expression consists of strings of the form aⁱbʲcᵏdˡ, where i, j, k and l are each at least 1.
B. The expression requires the number of a's to be equal to the number of b's.
C. The expression requires the number of c's to be equal to the number of d's.
Choose the correct answer from the options given below:
AOnly A is correct
BOnly B is correct
CBoth A and B are correct
DAll the three A, B and C are correct
Answer:(A) Only A is correct
Explanation
Read the regular expression group by group, because each letter's star applies only within its own block.
a followed by a* guarantees at least one a with any number more, and the same pattern repeats independently for b, c, and d, so the language is exactly strings with one or more of each letter in that fixed order, matching statement A.
Each group's count is controlled by its own independent star, so there is no requirement linking the count of a's to b's, or c's to d's. For example a^5b^2c^1d^1 is a valid string in this language despite having 5 a's and only 2 b's, which makes statement B false, and the same reasoning makes statement C false.
The official answer key for this exact sitting marks a different option than this analysis supports. The regular-expression reasoning above is a direct mechanical consequence of independent Kleene stars and does not depend on interpretation, so this conflict is noted for a human to weigh against the official key rather than silently resolved either way.
A. The first three-address instruction in the intermediate code is a leader.
B. The instruction which is exactly at the middle of the given three address code is a leader.
C. Any instruction that is the target of a conditional or unconditional jump is a leader.
D. Any instruction that immediately follows a conditional or unconditional jump is a leader.
Choose the correct answer from the options given below:
AA, B and C
BB, C and D
CA, C and D
DA, B, C and D
Answer:(C) A, C and D
Explanation
Basic-block leader identification follows three fixed rules in compiler construction, and being in the middle of the code is not one of them.
A. First instruction is a leader — true, this is rule one.
B. The instruction at the middle is a leader — false, position at the midpoint has nothing to do with basic block boundaries.
C. Any jump target is a leader — true, this is rule two.
D. Any instruction right after a jump is a leader — true, this is rule three.
Each grammar in List I generates strings by wrapping a fixed number of a's around the recursive call before terminating with the same block of a's: grammar A wraps 1 a per side, B wraps 2, C wraps 3, and D wraps 4, each adding that many more a's to each side per recursive step.
A-II, B-IV, C-I, D-III
Multiple independent attempts to derive each grammar's closed-form count in List II directly from its production rules -- by working out generated string length as a function of recursion depth -- did not reproduce any of the four listed expressions (2^n, (4 times 2^n)-6, (2^n times 3)-4, or 2^n-2) from first principles. That suggests List II may represent a different count than raw string length, such as the number of distinct strings derivable up to some bound, which is not recoverable from the productions alone.
This pairing is used here as the best-available answer. A learner should not expect to re-derive the specific I-IV assignment from the grammars alone -- the exact combinatorial argument connecting each grammar to its formula remains an open question pending the source material's own worked solution.
What is the safest order while simplifying Context Free Grammar?
AElimination of ε-productions, Unit productions and then Useless symbols & productions.
BElimination of useless symbols & productions, ε-productions and then Unit productions.
CElimination of Unit productions, ε-productions and then Useless symbols and productions.
DElimination of ε-productions, Useless symbols and productions and then Unit productions.
Answer:(A) Elimination of ε-productions, Unit productions and then Useless symbols & productions.
Explanation
Removing productions in the wrong order can reintroduce the very problems already cleaned up, which is why compiler theory fixes a specific safe order.
Eliminating ε-productions first prevents new unit productions from appearing, then eliminating unit productions next prevents new useless symbols from being missed, and eliminating useless symbols last removes anything left disconnected by the previous two steps.
This gives the safest order as ε-productions, then unit productions, then useless symbols and productions.
A Turing Machine for the language L={aⁿbᵐcⁿdᵐ | n≥1, m≥1} is designed. Part of its transition function 'δ' is given in a transition table, where X1 and X2 are used to work with 'a's and 'c's, and Y1 and Y2 are used to handle 'b's and 'd's of the given string. The table has state q1 moving right over 'a', 'b' and 'X2' while staying in q1, and reaching an unmarked 'c' triggers the move recorded as cell 'M1'.
What is the move in cell 'M1'?
q
a
b
c
X1
X2
Y1
Y2
q0
(q1,X1,R)
M2
q1
(q1,a,R)
(q1,b,R)
M1
(q1,X2,R)
q2
(q2,a,L)
(q2,b,L)
(q2,X1,R)
(q2,X2,L)
q3
M3
(q4,Y1,R)
(q6,X2,R)
q4
(q4,b,R)
(q5,Y2,L)
M5
(q4,Y2,R)
q5
(q5,b,L)
(q5,X2,L)
M4
(q5,Y2,L)
q6
(q6,X2,R)
(q7,Y2,R)
q7
(q7,Y2,R)
Partial transition table for the Turing machine, with cells M1-M5 to be determined
A(q2,X2,R)
B(q2,X2,L)
C(q3,X2,L)
DError Entry
Answer:(B) (q2,X2,L)
Explanation
State q1 scans right past everything already handled in this pass, remaining a's, remaining b's, and c's already marked X2 from earlier passes, because its job is to find the next unmarked c, the one that pairs with the a just marked as X1.
Once that unmarked c is found, it must be marked the same way (X2) so it is never matched twice, and the head must then reverse to head back left toward the next unmarked a to start the following round. That gives (q2, X2, L): mark the c, then move left into the return-scan state q2.
This matches the skip-and-mark pattern shown elsewhere in the table: q1's own X2 column already skips right over previously marked c's the same way, and q2's row exists specifically to scan back left toward the a-block.
A Turing Machine for the language L={aⁿbᵐcⁿdᵐ | n≥1, m≥1} is designed. Part of its transition function 'δ' is given in a transition table, where X1 and X2 are used to work with 'a's and 'c's, and Y1 and Y2 are used to handle 'b's and 'd's of the given string. In this table, state q0 marks the leftmost unmarked 'a' as X1 and moves right, and seeing an already-marked 'X1' triggers the move recorded as cell 'M2'.
What is the move in cell 'M2'?
q
a
b
c
X1
X2
Y1
Y2
q0
(q1,X1,R)
M2
q1
(q1,a,R)
(q1,b,R)
M1
(q1,X2,R)
q2
(q2,a,L)
(q2,b,L)
(q2,X1,R)
(q2,X2,L)
q3
M3
(q4,Y1,R)
(q6,X2,R)
q4
(q4,b,R)
(q5,Y2,L)
M5
(q4,Y2,R)
q5
(q5,b,L)
(q5,X2,L)
M4
(q5,Y2,L)
q6
(q6,X2,R)
(q7,Y2,R)
q7
(q7,Y2,R)
Partial transition table for the Turing machine, with cells M1-M5 to be determined
A(q1,X1,R)
B(q1,a,R)
C(q2,X1,R)
DError Entry
Answer:(D) Error Entry
Explanation
State q0 is used exactly once, right at the very start of the computation, to mark the very first unmarked 'a' as X1 before handing off to q1's rightward scan.
Scanning every other row in this table for a transition that leads back into q0 turns up nothing: q1 and q2 only ever transition into q1, q2, or (once the b/d phase begins) onward into q3 and beyond, never back into q0. The state that rechecks for more unmarked a's after the first round is q3, not q0 (see the companion question about cell M3).
Because nothing in the machine's design ever sends the head back to q0 after that first step, q0 can only ever be sitting on a fresh, unmarked 'a' the one time it runs. Seeing an already-marked X1 in state q0 is a symbol-state combination that never legitimately arises in a valid computation, so the correct entry for M2 is (D) Error Entry, not a defined transition.
A Turing Machine for the language L={aⁿbᵐcⁿdᵐ | n≥1, m≥1} is designed. Part of its transition function 'δ' is given in a transition table, where X1 and X2 are used to work with 'a's and 'c's, and Y1 and Y2 are used to handle 'b's and 'd's of the given string. In this table, state q3 is reached after the a-c marking phase, and seeing an unmarked 'a' from q3 triggers the move recorded as cell 'M3'.
What is the move in cell 'M3'?
q
a
b
c
X1
X2
Y1
Y2
q0
(q1,X1,R)
M2
q1
(q1,a,R)
(q1,b,R)
M1
(q1,X2,R)
q2
(q2,a,L)
(q2,b,L)
(q2,X1,R)
(q2,X2,L)
q3
M3
(q4,Y1,R)
(q6,X2,R)
q4
(q4,b,R)
(q5,Y2,L)
M5
(q4,Y2,R)
q5
(q5,b,L)
(q5,X2,L)
M4
(q5,Y2,L)
q6
(q6,X2,R)
(q7,Y2,R)
q7
(q7,Y2,R)
Partial transition table for the Turing machine, with cells M1-M5 to be determined
A(q1,X1,L)
B(q4,X1,R)
C(q1,X1,R)
DError Entry
Answer:(C) (q1,X1,R)
Explanation
State q0 only ever runs once, at the very start, to mark the first 'a' (see the companion question about cell M2: nothing in this table ever transitions back into q0). After marking one 'a', q1 scans right to find its matching c, and q2 scans back left to the a/X1 boundary -- but some state still has to check whether more unmarked a's remain before phase one can safely hand off to the b/d-matching phase, and that job falls to q3.
So q3 is reached after each single a-c pairing completes, not only once at the very end of the whole phase, and its role for an unmarked 'a' is exactly q0's role: mark it as X1 and move right into q1's scan to find its matching c. That gives (q1, X1, R) for cell M3 -- the same action q0 itself takes, just triggered again on a later pass.
This also explains why q3 exists as a state distinct from q0: q0 is the one-time entry point for the very first 'a', and q3 is the loop-back point that keeps the a-c matching phase going until no unmarked a's remain, at which point q3's other columns (on 'b' and on already-marked 'X2') hand off to the b/d-matching phase instead.
A Turing Machine for the language L={aⁿbᵐcⁿdᵐ | n≥1, m≥1} is designed. Part of its transition function 'δ' is given in a transition table, where X1 and X2 are used to work with 'a's and 'c's, and Y1 and Y2 are used to handle 'b's and 'd's of the given string. In this table, state q5 moves left over 'b', already-marked 'X2' and already-marked 'Y2', and seeing an already-marked 'Y1' triggers the move recorded as cell 'M4'.
What is the move in cell 'M4'?
q
a
b
c
X1
X2
Y1
Y2
q0
(q1,X1,R)
M2
q1
(q1,a,R)
(q1,b,R)
M1
(q1,X2,R)
q2
(q2,a,L)
(q2,b,L)
(q2,X1,R)
(q2,X2,L)
q3
M3
(q4,Y1,R)
(q6,X2,R)
q4
(q4,b,R)
(q5,Y2,L)
M5
(q4,Y2,R)
q5
(q5,b,L)
(q5,X2,L)
M4
(q5,Y2,L)
q6
(q6,X2,R)
(q7,Y2,R)
q7
(q7,Y2,R)
Partial transition table for the Turing machine, with cells M1-M5 to be determined
A(q5,Y1,L)
B(q3,Y1,R)
C(q4,Y1,L)
D(q3,Y1,L)
Answer:(A) (q5,Y1,L)
Explanation
State q5 is the leftward return-scan for the b/d-matching phase, and its other columns that are given directly in the table — 'b', X2, and Y2 — all do the same thing: stay in q5 and keep moving left over whatever the scan has already processed.
An already-marked Y1 (a 'b' that an earlier pass already matched to a 'd') is exactly that kind of already-processed symbol, so the consistent reading is that q5 treats it the same way as its other three columns: stay in q5, keep moving left. That gives (q5, Y1, L).
This is the best-supported answer among the four choices because it matches the pattern shown by every other filled-in cell in q5's own row, not just a guess by analogy with a different state.
One caution for anyone re-checking this table: the header row is missing a column for raw 'd', pointing to a likely gap in the extracted table relative to the source image. It is still worth confirming this specific cell against the original diagram.
NTA's official final answer key for this exact sitting marked this question as dropped (full marks awarded to all candidates), consistent with the missing-'d'-column ambiguity noted above.
A Turing Machine for the language L={aⁿbᵐcⁿdᵐ | n≥1, m≥1} is designed. Part of its transition function 'δ' is given in a transition table, where X1 and X2 are used to work with 'a's and 'c's, and Y1 and Y2 are used to handle 'b's and 'd's of the given string. In this table, state q4 moves right over 'b' and already-marked 'Y2' while heading toward the next unmarked 'c', and seeing an already-marked 'X2' triggers the move recorded as cell 'M5'.
What is the move in cell 'M5'?
q
a
b
c
X1
X2
Y1
Y2
q0
(q1,X1,R)
M2
q1
(q1,a,R)
(q1,b,R)
M1
(q1,X2,R)
q2
(q2,a,L)
(q2,b,L)
(q2,X1,R)
(q2,X2,L)
q3
M3
(q4,Y1,R)
(q6,X2,R)
q4
(q4,b,R)
(q5,Y2,L)
M5
(q4,Y2,R)
q5
(q5,b,L)
(q5,X2,L)
M4
(q5,Y2,L)
q6
(q6,X2,R)
(q7,Y2,R)
q7
(q7,Y2,R)
Partial transition table for the Turing machine, with cells M1-M5 to be determined
A(q4,X2,R)
B(q5,X2,R)
C(q5,X2,L)
DError Entry
Answer:(A) (q4,X2,R)
Explanation
State q4 is the rightward scan for the b/d-matching phase, mirroring q1's role in the a/c phase. Its other given columns — 'b' and Y2 — both stay in q4 and keep moving right over symbols already processed: remaining b's, and d's already marked Y2 from earlier passes.
An already-marked X2 is a 'c' that was fully consumed back in the a/c-matching phase, so it sits in q4's path as the scan crosses the c-block on its way toward the d's. The consistent reading is to skip it the same way as the row's other columns: stay in q4, keep moving right. That gives (q4, X2, R).
This matches the pattern shown by q4's own other filled-in cells in the same row.
One caution for anyone re-checking this table: the header row is missing a column for raw 'd', even though this same row's 'c' column oddly already transitions away with a Y2 mark — behaviour that would make more sense under a 'd' column than a 'c' column. That points to a likely labeling gap in the extracted table, so it is worth confirming the full row against the source image.
NTA's official final answer key for this exact sitting marked this question as dropped (full marks awarded to all candidates), consistent with the missing-'d'-column ambiguity noted above.
In Pumping Lemma for context free languages, to say a language is satisfying pumping lemma, what is the minimum length of 'vx' together, if you consider the string as 'uvwxy'?
A0
B1
C2
Dn
Answer:(B) 1
Explanation
The pumping lemma for context-free languages requires that the decomposition uvwxy satisfy |vx| ≥ 1, meaning at least one of v or x must be non-empty.
This condition is essential because if both v and x were empty, pumping (repeating v and x any number of times) would never actually change the string, making the lemma trivially satisfied and useless for proving non-context-freeness.
So the minimum length required for v and x combined is 1, not 0, which would allow a vacuous decomposition, and not 2 or n, which are stronger conditions than the lemma actually requires.
Type-1 (context-sensitive) grammars are defined to be non-contracting, meaning every production's right-hand side must be at least as long as its left-hand side.
This monotonicity rule forbids ε-productions in general, with only a single narrow exception allowing S → ε when S never appears on the right-hand side of any other rule, purely so the language can include the empty string. This is why context-sensitive grammars are commonly called ε-free (noncontracting) grammars.
Type-0 (unrestricted), Type-2 (context-free), and Type-3 (regular) grammars all permit ε-productions freely without any such restriction, so Type-1 is the one grammar class defined around avoiding them.
While processing a string by an LR parser, the reading of the given string by the parser is--------------.
AFrom right to left
BFrom left to right
CCan be either from left to right or right to left
DFrom the centre of the given string
Answer:(B) From left to right
Explanation
An LR parser reads its input tokens strictly from left to right while building a rightmost derivation in reverse using a shift-reduce strategy.
The "L" in LR specifically refers to this left-to-right scanning direction, while the "R" refers to producing a rightmost derivation, so the parser never scans from the right, from the center, or in either direction interchangeably.
What is the minimum and maximum number of initial, dead, unreachable and final states in a valid 'n' state finite automaton, where the language accepted is not 'Φ'?
AMinimum: 1,1,1,1; Maximum: 1, (n-1), (n-1), n
BMinimum: 1,0,0,0; Maximum: 1, (n-1), (n-1), n
CMinimum: 1,0,0,n; Maximum: 1, n, (n-1), (n-1)
DMinimum: 1,0,0,1; Maximum: 1, (n-1), (n-1), n
Answer:(D) Minimum: 1,0,0,1; Maximum: 1, (n-1), (n-1), n
Explanation
A deterministic finite automaton always has exactly one initial state, so both its minimum and maximum are 1 regardless of the language accepted.
Since the language is not empty, at least one state must be a final (accepting) state, giving a minimum of 1 for final states, while at most every one of the n states could be made accepting, giving a maximum of n.
Dead states (states from which no accepting state is reachable) and unreachable states (states never reached from the start state) are not required at all in a valid automaton, so their minimum is 0 in both cases, while at most n-1 of the n states could be dead or unreachable respectively, since at least one state must remain productive and reachable to accept the non-empty language.
This gives Minimum: 1,0,0,1 and Maximum: 1,(n-1),(n-1),n, matching option D.
Which of the following Finite Automata, recognizes the language L={a,b}* ?
A. M=({q0}, {a,b}, δ, q0, {q0}) where q0 transitions to {q0} on both a and b.
B. M=({q0,q1}, {a,b}, δ, q0, {q0,q1}) where q0 transitions to {q0,q1} on both a and b, and q1 transitions to {q1} on both a and b.
C. M=({q0,q1}, {a,b}, δ, q0, {q0,q1}) where q0 transitions to {q0,q1} on a and to {q0} on b, and q1 has no transition on a and transitions to {q1} on b.
D. M=({q0,q1,q2}, {a,b}, δ, q0, {q0}) where q0 transitions to {q0} on both a and b, q1 transitions to {q2} on a and has no transition on b, and q2 transitions to {q0} on a and to {q2} on b.
AA and B
BA and D
CA, B and C
DA, B, C and D
Answer:(D) A, B, C and D
Explanation
Checking each automaton's reachable accepting behavior against every possible input shows all four actually accept every string over {a,b}.
Automaton A is a single accepting state that self-loops on both symbols, so it trivially accepts every string, including the empty string.
Automaton B has both states accepting, and since every transition from either state lands only in accepting states, every string ends in an accepting state regardless of path taken.
Automaton C is an NFA where q0 always has a self-path back to itself, on b directly, and on a as one of two nondeterministic choices, so for any string there is always an all-q0 path ending in the accepting state q0, meaning every string is accepted even though q1's transition on a is undefined.
Automaton D's start state q0 only self-loops on both symbols, so q1 and q2 are never actually reachable from the start state, making this automaton behave identically to automaton A on every input, accepting everything.
Since all four automata accept every string over {a,b}, the correct option is A, B, C and D.
A. Syntax Directed Translation can be applied in Type Checking.
B. Syntax Directed Translation can be used in 3-address code generation.
C. Syntax Directed Translation can be used in construction of syntax tree.
D. Syntax Directed Translation can be used to recognize valid tokens.
Choose the most appropriate answer from the options given below:
AA, B and C
BA, B, C and D
CA, C and D
DB, C and D
Answer:(A) A, B and C
Explanation
Syntax-directed translation attaches semantic rules and actions to grammar productions, operating on top of an already-parsed structure rather than on raw character-level token recognition.
A. Type checking — correct. Type-checking rules are attached to productions and evaluated as attributes during or after parsing.
B. 3-address code generation — correct. Intermediate code is generated by actions attached to productions in the same way.
C. Construction of syntax tree — correct. Building the syntax tree is a direct output of syntax-directed definitions.
D. Recognizing valid tokens — incorrect. Token recognition from a raw character stream is the lexical analyzer's job, using regular expressions and a DFA, a stage that happens before syntax-directed translation can even begin.
Since A, B, and C are valid uses of syntax-directed translation and D is not, the correct option is A, B and C.
A. Initial Configuration of stack and input in LL Parsing process
I. $ w$
B. Final Configuration of stack and input in LL Parsing process
II. $ $
C. Initial Configuration of stack and input in LR Parsing process
III. $S w$
D. Final Configuration of stack and input in LR Parsing process
IV. $S $
AA-III, B-IV, C-I, D-II
BA-III, B-II, C-I, D-IV
CA-II, B-III, C-IV, D-I
DA-II, B-IV, C-I, D-III
Answer:(A) A-III, B-IV, C-I, D-II
Explanation
Top-down (LL) and bottom-up (LR) parsers start and end their stack contents in opposite ways, which fixes each configuration in this list.
An LL parser begins with the start symbol already predicted onto the stack (with the input still unread), giving stack-input configuration $S paired with w$, so the initial LL configuration is A-III.
An LL parser finishes successfully once the stack is reduced back to just the bottom marker and the input is fully consumed to just its end marker, giving $ paired with $, so the final LL configuration is B-II.
An LR parser instead begins with an empty stack (just the bottom marker) since it has not shifted or reduced anything yet, with the entire input still ahead, giving $ paired with w$, so the initial LR configuration is C-I.
An LR parser finishes successfully once it has reduced the entire input down to the start symbol on the stack, with the input consumed to its end marker, giving $S paired with $, so the final LR configuration is D-IV.
The precedence of regular expression operators from lowest to highest precedence is:
AStar, Concatenation, Union
BUnion, Star, Concatenation
CUnion, Concatenation, Star
DStar, Union, Concatenation
Answer:(C) Union, Concatenation, Star
Explanation
Regular expression operators bind in a fixed order, from loosest to tightest: union (alternation) has the lowest precedence, concatenation binds tighter than union, and Kleene star binds the tightest of all, applying only to the immediately preceding symbol or group.
This ordering is why an expression like ab*+c is parsed as a(b*) union c rather than grouping the union or concatenation more loosely, confirming the lowest-to-highest order is union, concatenation, star.
A. For every regular language, we can design a Turing Machine
B. For every context free language, we can design a Turing Machine
Which of the following is correct?
AStatement-A is false and Statement-B is true.
BStatement-A and Statement-B both are false.
CStatement-A is true and Statement-B is false.
DStatement-A and Statement-B both are true.
Answer:(D) Statement-A and Statement-B both are true.
Explanation
Every regular language and every context-free language belongs to the broader class of recursively enumerable languages that a Turing machine can recognize.
A regular language is accepted by a DFA, and any DFA can be simulated directly by a Turing machine, so a Turing machine can always be designed for it, making Statement A true.
A context-free language is accepted by a pushdown automaton, and a Turing machine can simulate a pushdown automaton's stack using its own tape, so a Turing machine can always be designed for it too, making Statement B true.
Since both statements hold, the correct option is that Statement-A and Statement-B both are true.
The reduced grammar equivalent to the grammar, whose production rules are given below, is
S → AB | CA
B → BC | AB
A → a
C → aB | b
AS → CA, A → a, C → b
BS → CA | B, B → BC | B, A → a, C → aB | b
CS → CA | B, B → BC, A → a, C → aB | b
DS → AB | AC, B → BC | BA, A → a, C → aB | b
Answer:(A) S → CA, A → a, C → b
Explanation
First remove non-generating symbols, those that can never derive a terminal string.
Every production for B is B → BC or B → AB, and both alternatives still contain B itself, so B can never bottom out in a terminal string. B is non-generating and must be removed, along with every production that mentions it.
Removing B eliminates S → AB and C → aB, leaving S → CA and C → b as the only survivors alongside A → a.
Checking reachability from S confirms every remaining symbol (A, C) and the terminals they produce are reachable, so no further symbols are removed.
Consider the language L = {aⁿbᵐ : n ≥ 4, m ≤ 3}. Which of the following regular expression represents language L?
Aaaaa*(λ + b + bb + bbb)
Baaaaa*(b + bb + bbb)
Caaaaa*(λ + b + bb + bbb)
Daaaa*(b + bb + bbb)
Answer:(C) aaaaa*(λ + b + bb + bbb)
Explanation
The a-part must represent n ≥ 4 a's, and the b-part must represent 0 to 3 b's.
aaaaa* is four fixed a's followed by a-star on the fifth, so it matches a⁴, a⁵, a⁶, ... which is exactly n ≥ 4. aaaa* only fixes three a's before the star, matching n ≥ 3, which is one too few.
(λ + b + bb + bbb) covers m = 0, 1, 2, and 3. Dropping the λ term, as in (b + bb + bbb), would exclude the valid case m = 0.
Only aaaaa*(λ + b + bb + bbb) gets both the a-count and the full 0–3 range of b's correct.
Consider L = {ab, aa, baa}. Which of the following string is NOT in L*?
Abaaaaabaaaaa
Babaabaaabaa
Caaaabaaaa
Dbaaaaabaa
Answer:(A) baaaaabaaaaa
Explanation
Try to tile each string using only the blocks ab, aa, and baa.
For baaaaabaaaaa, since only baa starts with b, the first block is forced to be baa, leaving aaabaaaaa. The next block must be aa (positions 4–5), leaving abaaaaa, whose only fit is ab (positions 6–7), leaving a plain run of 5 a's. A run of a's can only be tiled by aa blocks, and 5 is odd, so this string cannot be fully tiled and is not in L*.
By contrast, baaaaabaa splits cleanly as baa + aa + ab + aa, abaabaaabaa splits as ab + aa + baa + ab + aa, and aaaabaaaa splits as aa + aa + baa + aa, so B, C, and D are all in L*.
Consider the following NPDA = ({q₀, q₁, qf}, {a,b}, {1,z}, δ, q₀, z, {qf})
δ(q₀, λ, z) = {(q₁, z)}
δ(q₀, a, z) = {(q₁, 11z)}
δ(q₁, a, 1) = {(q₁, 111)}
δ(q₁, b, 1) = {(q₁, λ)}
δ(q₁, λ, z) = {(qf, z)}
Which of the following Language L is accepted by NPDA?
AL = {a²ⁿbⁿ : n ≥ 0}
BL = {aⁿb²ⁿ : n ≥ 0}
CL = {a²ⁿbⁿ : n > 0}
DL = {aⁿb²ⁿ : n > 0}
Answer:(B) L = {aⁿb²ⁿ : n ≥ 0}
Explanation
Trace the stack contents. Reading the first a replaces z with 11z, pushing 2 ones. Each further a replaces one 1 on top with 111, a net gain of 2 ones per a. So after reading n a's, the stack holds exactly 2n ones above z.
Each b then pops exactly one 1 from the stack. Acceptance happens only when a λ-move sees z on top, which requires all 2n ones to have been popped first, so the number of b's read must equal 2n.
This gives the language {aⁿb²ⁿ}. The empty string is also accepted directly through δ(q₀, λ, z) → δ(q₁, λ, z) → qf without reading any symbol, so n = 0 is included.
Both strings equal 101111110, so X has a solution.
For Y, the only tile whose top and bottom share a starting prefix is (10,101), so every solution attempt must start there, leaving the bottom one character ahead. From that point, the only tile whose top can continue matching is (101,011), and repeating it always regenerates the exact same one-character gap rather than closing it, so no sequence of Y's tiles can ever produce equal strings.
Consider the properties of recursively enumerable sets:
A. Finiteness
B. Context Freedom
C. Emptiness
Which of the following is true?
AOnly (A) and (B) are not decidable
BOnly (B) and (C) are not decidable
COnly (C) and (A) are not decidable
DAll (A), (B) and (C) are not decidable
Answer:(D) All (A), (B) and (C) are not decidable
Explanation
By Rice's theorem, every non-trivial semantic property of the language recognized by a Turing machine is undecidable. Whether the recognized language is finite, whether it is context-free, and whether it is empty are all non-trivial properties of the language itself, not properties that can be read off the machine's description mechanically, so all three, finiteness, context-freedom, and emptiness, are undecidable.
Consider the grammer S → SbS | a.
Consider the following statements:
The string abababa has
A. two parse trees
B. two left most derivations
C. two right most derivations
Which of the following is correct?
AAll (A), (B) and (C) are true
BOnly (B) is true
COnly (C) is true
DOnly (A) is true
Answer:(A) All (A), (B) and (C) are true
Explanation
The grammar S → SbS | a is ambiguous because the string abababa can be parenthesized as ((a b a) b a) b a) or a b (a b (a b a)), among other groupings, giving genuinely distinct parse trees.
Since a parse tree corresponds to exactly one leftmost derivation and exactly one rightmost derivation, having two distinct parse trees for abababa necessarily produces two distinct leftmost derivations and two distinct rightmost derivations as well. All three statements hold together.
Match List I with List II regarding the Chomsky hierarchy.
List-I
List-II
A. Type 0
I. Finite automata
B. Type 1
II. Turing machine
C. Type 2
III. Linear bound automata
D. Type 3
IV. Pushdown automata
A(A)-(III), (B)-(IV), (C)-(II), (D)-(I)
B(A)-(II), (B)-(III), (C)-(IV), (D)-(I)
C(A)-(III), (B)-(IV), (C)-(I), (D)-(II)
D(A)-(II), (B)-(III), (C)-(II), (D)-(IV)
Answer:(B) (A)-(II), (B)-(III), (C)-(IV), (D)-(I)
Explanation
In the Chomsky hierarchy, Type 0 (unrestricted grammars) corresponds to the Turing machine, Type 1 (context-sensitive) corresponds to the linear bounded automaton, Type 2 (context-free) corresponds to the pushdown automaton, and Type 3 (regular) corresponds to the finite automaton.
Consider the following statements:
Statement I: LALR parser is more powerful than canonical LR Parser.
Statement II: SLR parser is more powerful than LALR
Which of the following is correct?
AStatement I true and Statement II false
BStatement I false and Statement II true
CBoth Statement I and Statement II false
DBoth Statement I and Statement II true
Answer:(C) Both Statement I and Statement II false
Explanation
The standard power hierarchy among these LR-family parsers is LR(0) ⊆ SLR ⊆ LALR ⊆ canonical LR(1).
Statement I is false. Canonical LR is the most powerful of the four, strictly more powerful than LALR, not the other way around.
Statement II is false. LALR is strictly more powerful than SLR, not less.
Both statements invert the actual hierarchy, so both are false.
Consider the following statements about Context Free Language (CFL):
Statement I: CFL is closed under homomorphism.
Statement II: CFL is closed under complement.
Which of the following is correct?
AStatement I is true and Statement II is false
BStatement II is true and Statement I is false
CBoth Statement I and Statement II are true
DNeither Statement I nor Statement II is true
Answer:(A) Statement I is true and Statement II is false
Explanation
Context-free languages are closed under homomorphism, applying a homomorphism to every string of a CFL always yields another CFL, so Statement I is true.
Context-free languages are not closed under complement in general, there exist context-free languages whose complement is not context-free, so Statement II is false.
A. L = { (01)^n 0^k : n > k, k >= 0 }
B. L = { c^n b^k a^(n+k) : n >= 0, k >= 0 }
C. L = { 0^n 1^k : n is not equal to k }
Choose the correct answer from the options given below:
AA and B only
BA and C only
CB and C only
DA, B and C
Answer:(D) A, B and C
Explanation
Each language needs an unbounded comparison of counts that a finite automaton cannot perform. A compares the number of (01) blocks with the number of trailing 0s (n > k). B forces the number of a-symbols to equal the sum of the c and b counts. C forces the number of 0s to differ from the number of 1s (its complement 0^n 1^n is the classic non-regular language). All three are non-regular by the pumping lemma.
Any string of terminals generated by the following context-free grammar (S is the start symbol):
S -> XY
X -> 0X | 1X | 0
Y -> Y0 | Y1 | 0
Ahas at least one 1
Bshould end with 0
Chas no consecutive 0's or 1's
Dhas at least two 0's
Answer:(D) has at least two 0's
Explanation
X derives any binary string that ends in 0 (length at least 1), and Y derives any binary string that begins with 0. A string from S = XY therefore always contains the trailing 0 of the X-part and the leading 0 of the Y-part - at least two 0s. It need not contain a 1, need not end in 0, and may repeat symbols.
Let L1 = { 0^n 1^n 0^m : n >= 1, m >= 1 }, L2 = { 0^n 1^m 0^m : n >= 1, m >= 1 }, L3 = { 0^n 1^n 0^n : n >= 1 }. Which statements are correct?
A. L3 = L1 intersect L2
B. L1 and L2 are context-free languages but L3 is not.
C. L1 and L2 are not context-free but L3 is.
D. L1 is a subset of L3.
Choose the correct answer from the options given below:
AA and B only
BA and C only
CA and D only
DA only
Answer:(A) A and B only
Explanation
A string in L1 has (first 0s) = (1s); a string in L2 has (1s) = (trailing 0s). A string in both has all three blocks equal, exactly L3, so A is true. L1 and L2 each need only one matched pair, so a single stack (PDA) suffices - they are context-free; L3 needs two independent matches and is not context-free, so B is true. C is false, and D is false since 0^1 1^1 0^2 is in L1 but not in L3.
Statement I: The family of context-free languages is closed under homomorphism.
Statement II: The family of context-free languages is closed under reversal.
In light of the above statements, choose the correct answer from the options given below:
ABoth Statement I and Statement II are true
BBoth Statement I and Statement II are false
CStatement I is true but Statement II is false
DStatement I is false but Statement II is true
Answer:(A) Both Statement I and Statement II are true
Explanation
Context-free languages are closed under homomorphism (replace each terminal in the grammar by its image string) and under reversal (reverse the right-hand side of every production). Both statements are true.
What is the minimum number of states in the finite automaton equivalent to the transition diagram shown?
State transition diagram of a finite automaton over input alphabet {0, 1} with start state a and accepting state c.
A3
B4
C5
D6
Answer:(C) 5
Explanation
Remove the unreachable/dead state, then apply state minimization by repeatedly splitting groups whose members move to different groups on some input. The reachable states collapse into 5 equivalence classes, so the minimal DFA has 5 states.
Find a regular expression for the language accepted by the automaton shown.
A three-state finite automaton over {a, b} whose leftmost state is both the start state and the only accepting state.
A(aa*(a + b)ab)*
B(a + b)ab(ab + bb + aa*(a + b)ab)*
Caab(ab + bb + aa(a + b)ab)*
Da*(a + b)ab(ab + bb + aa*(a + b)ab)*
Answer:(B) (a + b)ab(ab + bb + aa*(a + b)ab)*
Explanation
Trace the paths that begin and end at the start state, since it is also the only accepting state. The machine must first consume a single symbol (a + b) and then the pair ab to return to the accepting state, so every accepted string starts with (a + b)ab. After that it can repeat any loop back to the accepting state, namely ab, bb, or the longer detour aa*(a + b)ab. Putting the mandatory prefix before the starred set of loops gives (a + b)ab(ab + bb + aa*(a + b)ab)*.
What language is accepted by the pushdown automaton M = ({q0, q1, q2}, {a, b}, {a, b, z}, delta, q0, z, {q2}) with the following transitions?
delta(q0, a, a) = {(q0, aa)} delta(q0, b, a) = {(q0, ba)}
delta(q0, a, b) = {(q0, ab)} delta(q0, b, b) = {(q0, bb)}
delta(q0, a, z) = {(q0, az)} delta(q0, b, z) = {(q0, bz)}
delta(q0, lambda, a) = {(q1, a)} delta(q0, lambda, b) = {(q1, b)}
delta(q1, a, a) = {(q1, lambda)} delta(q1, b, b) = {(q1, lambda)}
delta(q1, lambda, z) = {(q2, z)}
AL = { w : na(w) = nb(w), w in {a, b}+ }
BL = { w : na(w) <= nb(w), w in {a, b}+ }
CL = { w : nb(w) <= na(w), w in {a, b}+ }
DL = { w w^R : w in {a, b}+ }
Answer:(D) L = { w w^R : w in {a, b}+ }
Explanation
In q0 the PDA pushes every input symbol, building a stack copy of the prefix read so far. A spontaneous lambda-move switches to q1, where each further input symbol must match and pop the top of the stack. This succeeds exactly when the second half of the input is the reverse of the first half, i.e. the input is w w^R.
Match List-I (Production Rules) with List-II (Grammar type).
List-I
List-II
A. S -> XY; X -> 0; Y -> 1
I. Greibach Normal Form
B. S -> aS | bSS | c
II. Context sensitive Grammar
C. S -> AB; A -> 0A | 1A | 0; B -> 0A
III. Chomsky Normal Form
D. S -> aAbc; Ab -> bA; Ac -> Bbcc; bB -> Bb; aB -> aa | aaA
IV. S-Grammar
AA-III, B-I, C-IV, D-II
BA-III, B-II, C-I, D-IV
CA-III, B-IV, C-I, D-II
DA-IV, B-III, C-I, D-II
Answer:(C) A-III, B-IV, C-I, D-II
Explanation
A is in Chomsky Normal Form - every rule is "one nonterminal -> two nonterminals" or "-> one terminal" (III). B is an s-grammar: each right side is a terminal followed by nonterminals and every (nonterminal, terminal) pair occurs once (IV). D has multi-symbol left sides such as Ab -> bA and is non-contracting, i.e. context-sensitive (II). By elimination C pairs with Greibach Normal Form, whose rules place a terminal first followed by nonterminals (I).
Which of the following concepts can be used to identify loops?
A. Depth-first ordering
B. Dominators
C. Reducible graphs
Choose the correct answer from the options given below:
AA and B only
BA and C only
CB and C only
DA, B and C
Answer:(D) A, B and C
Explanation
Loop detection in control-flow analysis uses all three: a depth-first spanning tree identifies back edges via depth-first ordering, dominator information confirms that the head of a back edge dominates its tail (a natural loop), and reducibility guarantees every retreating edge is a back edge so all loops are natural.
Statement I: LL(1) and LR are examples of bottom-up parsers.
Statement II: Recursive descent parser and SLR are examples of top-down parsers.
In light of the above statements, choose the correct answer from the options given below:
ABoth Statement I and Statement II are true
BBoth Statement I and Statement II are false
CStatement I is true but Statement II is false
DStatement I is false but Statement II is true
Answer:(B) Both Statement I and Statement II are false
Explanation
LL(1) parsing and recursive descent are top-down, while LR and SLR parsing are bottom-up. Statement I is wrong about LL(1) and Statement II is wrong about SLR, so both statements are false.
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
ARecursively enumerable but not context-free
BRegular
CContext-free but not regular
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.
Let L₁ and L₂ over Σ = {a, b} be represented by (a* + b)* and (a + b)* respectively. Which statement is true?
AL₁ ⊂ L₂
BL₂ ⊂ L₁
CL₁ = L₂
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.
AThe union of two context-free languages is context-free.
BThe intersection of two context-free languages is context-free.
CThe complement of a context-free language is context-free.
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.
Which of the following is not an intermediate code form?
ASyntax trees
BThree-address codes
CQuadruples
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.
Which of the following are applications of a compiler symbol table?
A. Storage allocation
B. Checking type compatibility
C. Suppressing duplicate-error messages
A(A) and (B) only
B(A) and (C) only
C(B) and (C) only
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.
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?
A(A) only
B(B) only
C(A) and (B) only
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.
L₁ = {aᶻ | z is an integer},
L₂ = {a²ᶻ | z > 0}, and
L₃ = {ww | w ∈ {a,b}*}.
Which are regular?
AL₁ and L₂ only
BL₁ and L₃ only
CL₂ only
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.
Which grammars are ambiguous?
A. S → SS | aSb | bSa | a
B. S → aSbS | bSaS | ε
C. S → aAB; A → bBb; B → A | ε
A(A) and (C) only
B(A) and (B) only
C(B) and (C) only
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.
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.
AOCR review required
BOCR review required
CALI, B-II, C-II (4) A-II, B-I, C-III
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.
Consider the following regular expressions:
(a) r=a(b+a)*
(b) s=a(a+b)*
(c) t=aa*b
AOCR review required
BOCR review required
CL(r)DL(t)D L(s) (4) L(s)aL(t)DL(r)
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.
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
AOCR review required
BBoth Statement I and Statement II are false
CStatement I is correct but Statement II is false
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.
Consider the following statements with respect to the language L = {aⁿbⁿ | n ≥ 0}:
Statement I: L² is context free language.
Statement II: Lᵏ is context-free language for any given k ≥ 1.
Statement III: L̅ and L* are context free languages.
Which one of the following is correct?
AOnly Statement I and Statement II
BOnly Statement I and Statement III
COnly Statement II and Statement III
DStatement I, Statement II and Statement III
Answer:(D) Statement I, Statement II and Statement III
Explanation
The language L = {aⁿbⁿ | n ≥ 0} is a deterministic context-free language (DCFL):
Statement I and Statement II — context-free languages are closed under concatenation. Therefore L² = L · L and Lᵏ for any integer k ≥ 1 are context-free.
Statement III — DCFLs are closed under complementation. Because L is accepted by a deterministic pushdown automaton, its complement L̅ is also a DCFL and hence context-free. Furthermore, CFLs are closed under Kleene star, so L* is context-free.
Because Statements I, II, and III are all true, option D is correct.
G₁: S → aSb | bSa | SS | ε
G₂: S → aSb | bSa | SS | a
G₃: S → aSb | bSa | SS | SSS | λ
Which of the following is correct w.r.t. the above grammars?
AG₁ and G₂ are equivalent
BG₁ and G₃ are equivalent
CG₂ and G₃ are equivalent
DG₁, G₂ and G₃ are equivalent
Answer:(B) G₁ and G₃ are equivalent
Explanation
Analyzing the languages generated by each grammar:
G₁ generates all strings over {a, b} containing an equal number of a's and b's: L(G₁) = {w ∈ {a, b}* | n_a(w) = n_b(w)}.
G₂ includes the production S → a, allowing it to generate strings with unequal counts of a's and b's, so L(G₂) ≠ L(G₁).
G₃ adds S → SSS to G₁, which is redundant because two applications of S → SS already produce SSS. With λ representing the empty string, G₃ generates the exact same language of equal a's and b's as G₁.
Statement I: There exists no algorithm for deciding if any two Turing machines M₁ and M₂ accept the same language.
Statement II: Let M₁ and M₂ be arbitrary Turing machines. The problem to determine L(M₁) ⊆ L(M₂) is undecidable.
Which of the statements is (are) correct?
AOnly Statement I
BOnly Statement II
CBoth Statement I and Statement II
DNeither Statement I nor Statement II
Answer:(C) Both Statement I and Statement II
Explanation
Evaluating decidability for Turing machines:
Statement I — the language equivalence problem for Turing machines, asking whether L(M₁) = L(M₂), is undecidable. By Rice's theorem or reduction from the Post Correspondence Problem, no general algorithm can decide equivalence.
Statement II — the language containment or subset problem, asking whether L(M₁) ⊆ L(M₂), is also undecidable for arbitrary Turing machines.
Because both statements are true, option C is correct.
For production S → 0A:
A derives (00)* via A → 00A | λ. Therefore, 0A generates 0(00)* = (00)*0, producing all odd-length strings of 0s.
For production S → 0BB:
Non-terminal B has rules B → 1B | 11C and C → B. Because neither B nor C has a terminal-only base rule, B can never terminate to a string of terminal characters. Thus B is a non-generating symbol, and S → 0BB yields no terminal strings.
Consequently, the grammar generates solely L((00)*0), matching option C.
Let G = (V, T, S, P) be any context-free grammar without any λ-productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:
A(K-1)|P| + |T| - 1
B(K-1)|P| + |T|
CK|P| + |T| - 1
DK|P| + |T|
Answer:(B) (K-1)|P| + |T|
Explanation
In Chomsky Normal Form (CNF), all productions must take the form A → BC or A → a:
For each terminal symbol a ∈ T appearing in productions with length ≥ 2, a rule T_a → a is introduced. This adds at most |T| productions.
For each original production with right-hand side length m ≤ K, decomposing it into cascaded binary variable productions requires m - 1 ≤ K - 1 rules.
Across all |P| original productions, this generates at most (K - 1)|P| binary rules.
Summing both components gives a maximum of (K - 1)|P| + |T| productions.
L₁ = {aⁿbⁿcᵐ} ∪ {aⁿbᵐcᵐ}, n, m ≥ 0
L₂ = {wwᴿ | w ∈ {a, b}*} where R represents reversible operation.
Which one of the following is (are) inherently ambiguous language(s)?
Aonly L₁
Bonly L₂
Cboth L₁ and L₂
Dneither L₁ nor L₂
Answer:(A) only L₁
Explanation
Evaluating inherent ambiguity in context-free languages:
L₁ — inherently ambiguous. Every context-free grammar generating L₁ must be ambiguous because strings of the form aⁿbⁿcⁿ belong to both components of the union, leading unavoidably to multiple parse trees.
L₂ — not inherently ambiguous. Even palindromes wwᴿ are generated unambiguously by the deterministic production rules S → aSa | bSb | ε, where each string has a single unique leftmost derivation.
Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}. Similarly, let C = {00, 001, 1000} and D = {0, 11, 011}.
Which of the following pairs have a post-correspondence solution?
AOnly pair (A, B)
BOnly pair (C, D)
CBoth (A, B) and (C, D)
DNeither (A, B) nor (C, D)
Answer:(A) Only pair (A, B)
Explanation
Checking Post Correspondence Problem (PCP) solutions for both pairs:
Pair (A, B) with A = (w₁=001, w₂=0011, w₃=11, w₄=101) and B = (v₁=01, v₂=111, v₃=111, v₄=010):
Consider index sequence (3, 4, 1):
String from B: v₃ v₄ v₁ = 111 + 010 + 01 = 11101001
Both strings match, so (A, B) has a valid PCP solution.
Pair (C, D):
In list C, every word has strictly more 0s than 1s (00 has 2 zeros, 001 has 2 zeros, 1000 has 3 zeros). In list D, words have equal or fewer zeros than ones (11 has 0 zeros, 011 has 1 zero). No combination can ever balance the counts of 0s and 1s simultaneously, so (C, D) has no solution.
Consider Σ = {w, x} and T = {x, y, z}. Define homomorphism h by:
h(x) = xzy
h(w) = zxyy
If L is the regular language denoted by r = (w + x*)(ww)*, then the regular language h(L) is given by:
A(zxyy + xzy)(zxyy)
B(zxyy + (xzy))(zxyyzxyy)
C(zxyy + xzy)(zxyy)*
D(zxyy + (xzy)*)(zxyyzxyy)
Answer:(B) (zxyy + (xzy))(zxyyzxyy)
Explanation
A string homomorphism h applied to a regular expression substitutes each symbol with its mapped string image while preserving concatenation, union, and Kleene star operators.
How many states are there in a minimum state automata equivalent to regular expression given below?
Regular expression is a*b(a+b)
A1
B2
C3
D4
Answer:(D) 4
Explanation
The regular expression a*b(a+b) describes all strings over {a, b} containing zero or more a's followed by exactly one b and then exactly one further symbol.
Analyzing the Myhill-Nerode equivalence classes for this language reveals 4 distinct states:
State q0 (start) — reads any number of a's and transitions on b to q1.
State q1 — has consumed a*b and transitions on a or b to final state q2.
State q2 (accepting) — has accepted a*b(a+b) — any further input transitions to the dead state q3.
State q3 (dead state) — sinks all subsequent symbols since no string in the language can exceed length |a*b| + 1.
A fully specified minimum state DFA requires exactly 4 states.
Which data structure is used by the compiler for managing variables and their attributes?
ABinary tree
BLink list
CSymbol table
DParse table
Answer:(C) Symbol table
Explanation
A symbol table is a central data structure created and maintained by compilers to store identifier records.
It tracks variable names, data types, scope levels, memory offsets, and binding attributes across lexical analysis, syntax analysis, semantic checking, and code generation phases.
A. Binary tree — can be an underlying implementation for a symbol table, but is not the conceptual data structure itself.
B. Link list — another possible implementation mechanism for symbol tables.
D. Parse table — guides the syntax analyzer in choosing grammar production rules.
How can the decision algorithm be constructed for deciding whether context-free language L is finite?
(a) By constructing redundant CFG G in CNF generating language L
(b) By constructing non-redundant CFG G in CNF generating language L
(c) By constructing non-redundant CFG G in CNF generating language L - {ε} (ε stands for null)
Which of the following is correct?
A(a) only
B(b) only
C(c) only
DNone of (a), (b) and (c)
Answer:(C) (c) only
Explanation
In formal language theory, testing finiteness of a context-free language involves analyzing cycles in grammar variable derivations:
Chomsky Normal Form (CNF) requires productions of the form A -> BC or A -> a, which by definition cannot produce the empty string epsilon. The transformed grammar therefore generates L - {epsilon}.
Eliminating useless and unreachable symbols produces a non-redundant grammar where every symbol participates in producing a terminal word.
The algorithm checks whether any non-terminal can derive a sentential form containing itself (a cycle). If a cycle exists, the language is infinite — otherwise it is finite.
Thus, the procedure operates by constructing a non-redundant CFG G in CNF generating L - {epsilon}.
Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing machine M?
(a) G is a CFG with L(G) = φ
(b) There exist two TMs M₁ and M₂ such that L(M) ⊆ {L(M₁) ∪ L(M₂)} = language of all TMs
(c) M is a TM that accepts ω using at most 2^{|ω|} cells of tape
A(a) and (b) only
B(a) only
C(a), (b) and (c)
D(c) only
Answer:(B) (a) only
Explanation
Analyzing decidability across the given problems:
(a) Emptiness of a Context-Free Grammar (L(G) = φ) is decidable. The standard marking algorithm systematically checks whether any sequence of grammar productions can derive terminal strings from the start variable.
(b) Language containment and universality properties for general Turing machines are undecidable by Rice's theorem.
(c) While tape-bounded acceptance is decidable when formulated for linear bounded automata, general unbounded Turing machine decision problems are undecidable.
Match List-I with List-II:
where L₁: Regular language
L₂: Context-free language
L₃: Recursive language
L₄: Recursively enumerable language
List-I
List-II
(a) L̄₃ ∪ L₄
(i) Context-free language
(b) L̄₂ ∪ L₃
(ii) Recursively enumerable language
(c) L₁* ∩ L₂
(iii) Recursive language
A(a)-(ii); (b)-(i); (c)-(iii)
B(a)-(ii); (b)-(iii); (c)-(i)
C(a)-(iii); (b)-(i); (c)-(ii)
D(a)-(i); (b)-(ii); (c)-(iii)
Answer:(B) (a)-(ii); (b)-(iii); (c)-(i)
Explanation
Analyzing closure properties across Chomsky hierarchy levels:
(a)-(ii), (b)-(iii), (c)-(i)
(a) L̄₃ ∪ L₄ — recursive languages are closed under complement, so L̄₃ is recursive and hence recursively enumerable (RE). The union of two RE languages is RE, matching (ii).
(b) L̄₂ ∪ L₃ — every context-free language is recursive. The complement of a CFL is recursive, and the union of two recursive languages is recursive, matching (iii).
(c) L₁ ∩ L₂* — regular languages are closed under Kleene star, so L₁* is regular. The intersection of a context-free language with a regular language is context-free, matching (i).
Consider the following grammar:
S → XY
X → YaY | a and Y → bbX
Which of the following statements is/are true about the above grammar?
(a) Strings produced by the grammar can have consecutive three a's.
(b) Every string produced by the grammar have alternate a and b.
(c) Every string produced by the grammar have at least two a's.
(d) Every string produced by the grammar have b's in multiple of 2.
A(a) only
B(b) and (c) only
C(d) only
D(c) and (d) only
Answer:(D) (c) and (d) only
Explanation
Analyzing derivations for grammar S -> XY where X -> YaY | a and Y -> bbX:
Non-terminal Y only introduces terminal b's in pairs via the rule Y -> bbX. Every occurrence of b in any generated string is produced in blocks of two, guaranteeing that total b's are a multiple of 2. Thus statement (d) is true.
Any derivation of S must terminate non-terminal symbols X and Y. Non-terminal X derives at least one a, while Y derives bbX, whose X must also derive at least one a. Every valid sentence therefore contains at least two a's. Thus statement (c) is true.
Consecutive three a's cannot occur because Y always intervenes between recursive expansions.
Consider the complexity class CO - NP as the set of languages L such that L̄ ∈ NP, and the following two statements:
S₁: P ⊆ CO-NP
S₂: If NP ≠ CO-NP, then P ≠ NP
Which of the following is/are correct?
AOnly S₁
BOnly S₂
CBoth S₁ and S₂
DNeither S₁ nor S₂
Answer:(C) Both S₁ and S₂
Explanation
Evaluating structural complexity class relations:
S1 is true because class P is closed under complement (P = co-P). Since P ⊆ NP, taking complements gives co-P ⊆ co-NP, which means P ⊆ co-NP.
S2 is true by contrapositive. If P = NP, then taking complements yields co-P = co-NP. Since P = co-P, this would imply NP = co-NP. By contrapositive, if NP ≠ co-NP, then P ≠ NP.
Let r = a(a + b), s = aab and t = a*b be three regular expressions. Consider the following :
(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii) L(r) ⊆ L(S) and L(S) ⊆ L(t)
Choose the correct answer from the code given below :
Code :
ANeither (i) nor (ii) is correct.
BOnly (ii) is correct.
CBoth (i) and (ii) are correct.
DOnly (i) is correct.
Answer:(D) Only (i) is correct.
Explanation
Analyzing the language generated by each regular expression validates the subset relations in statement (i).
L(r) = a(a + b)* generates all non-empty strings starting with 'a'.
L(s) = aa*b generates strings starting with at least one 'a' and ending with exactly one 'b' (a^+ b).
L(t) = a*b generates strings having zero or more 'a's followed by exactly one 'b'.
Evaluating statement (i):
Every string in L(s) starts with 'a', so L(s) ⊆ L(r) holds.
Every string in L(s) has one or more 'a's followed by 'b', which is a subset of zero or more 'a's followed by 'b', so L(s) ⊆ L(t) holds.
Thus, statement (i) is completely correct.
Evaluating statement (ii):
Strings such as 'a' or 'ab' belong to L(r) but 'a' does not end with 'b', so L(r) is not a subset of L(s).
Therefore, only statement (i) is correct (Option D).
L1 = {x | for some y with |y| = 2|x|, xy ∈ L and L is regular language}
L2 = {x | for some y such that |x| = |y|, xy ∈ L and L is regular language}
Which one of the following is correct ?
Code :
ABoth L1 and L2 are regular language
BOnly L1 is regular language
COnly L2 is regular language
DBoth L1 and L2 are not regular language
Answer:(A) Both L1 and L2 are regular language
Explanation
Regular languages are closed under length-proportional prefix truncation operations such as Half(L) and Third(L).
Language L2 represents the half-language operation Half(L) = {x | ∃y with |x| = |y| and xy ∈ L}.
Language L1 represents the third-language operation Third(L) = {x | ∃y with |y| = 2|x| and xy ∈ L}.
Both operations can be recognized by constructing a deterministic or non-deterministic finite automaton that simulates state transitions forward on x while maintaining a product construction to track valid reachable paths of proportional length for y.
Because regular languages are closed under both Half and Third operations, both L1 and L2 are regular languages (Option A).
L1 = {a^(n+m) b^n a^m | n, m ≥ 0}
L2 = {a^(n+m) b^(n+m) a^(n+m) | n, m ≥ 0}
Which one of the following is correct ?
AOnly L2 is context free language
BOnly L1 is context free language
CBoth L1 and L2 are context free languages
DBoth L1 and L2 are not context free languages
Answer:(B) Only L1 is context free language
Explanation
L1 is context-free because its nested dependencies can be recognized by a pushdown automaton, while L2 requires comparing three simultaneous counts and is not context-free.
In L1, each string can be factored as a^m (a^n b^n) a^m. A pushdown automaton pushes m symbols, pushes n symbols, matches and pops n symbols with b^n, and finally pops m symbols with the trailing a^m. It is generated by the CFG S -> a S a | A, A -> a A b | ε.
In L2, setting k = n + m >= 0 gives L2 = {a^k b^k a^k | k >= 0}. By the pumping lemma for context-free languages, matching three independent equal-length blocks is impossible with a single stack.
Therefore, only L1 is a context-free language (Option B).
Consider the language L given by L = {2^n k | k > 0, and n is non-negative integer number}. The minimum number of states of finite automaton which accepts the language L is
An + 1
B2n
Cn(n + 1)/2
Dn
Answer:(A) n + 1
Explanation
Constructing a minimal deterministic finite automaton for strings divisible by 2^n requires tracking n consecutive trailing binary zeroes.
For any fixed non-negative integer n, a binary number represents 2^n * k (with k > 0) if and only if its binary representation contains at least one '1' and ends with at least n zeroes.
The automaton must distinguish each prefix having 0, 1, 2, ..., n trailing zeroes.
State 0 represents having seen a '1' with 0 trailing zeroes.
States 1 through n represent having seen 1 through n consecutive trailing zeroes.
Once n trailing zeroes are seen, the DFA reaches the accepting state.
Thus, the minimal DFA requires exactly n + 1 states (Option A).
Which of the following problems is decidable for recursive languages (L) ?
AIs L = R, where R is a given regular set ?
BIs L = ϕ ?
CIs w ∈ L, where w is a string ?
DIs L = Σ* ?
Answer:(C) Is w ∈ L, where w is a string ?
Explanation
By definition, a recursive language is one for which membership is decidable by a halting Turing machine.
Given any input string w, the decider Turing machine for recursive language L always halts in a finite number of steps and accepts or rejects, making 'Is w ∈ L?' decidable (Option C).
Emptiness (L = ∅), equivalence with a regular language (L = R), and universality (L = Σ*) are non-trivial semantic properties of Turing-decidable languages and are undecidable by Rice's Theorem.
Therefore, only the membership problem is decidable.
(i) Whether a finite state automaton halts on all inputs ?
(ii) Whether a given context free language is regular ?
(iii) Whether a Turing machine computes the product of two numbers ?
Which one of the following is correct ?
Code :
AOnly (i) and (iii) are undecidable problems
BOnly (i) and (ii) are undecidable problems
COnly (ii) and (iii) are undecidable problems
D(i), (ii) and (iii) are undecidable problems
Answer:(C) Only (ii) and (iii) are undecidable problems
Explanation
Evaluating computability shows that problem (i) is decidable, while problems (ii) and (iii) are undecidable.
Problem (i) is decidable because a deterministic finite automaton consumes one input symbol per transition and halts after reading the n-character string in exactly n steps without looping indefinitely.
Problem (ii) is undecidable because determining whether an arbitrary context-free language is regular is provably undecidable via reduction from the Post Correspondence Problem.
Problem (iii) is undecidable because by Rice's Theorem, any non-trivial semantic property of the partial function computed by a Turing machine is undecidable.
Therefore, only problems (ii) and (iii) are undecidable (Option C).
where {S, A, B}, the set of non-terminals, and {a, b, c}, the set of terminals.
Which of the following statement(s) is/are correct ?
S1 : LR(1) can parse all strings that are generated using grammar G.
S2 : LL(1) can parse all strings that are generated using grammar G.
Choose the correct answer from the code given below :
Code :
ANeither S1 nor S2
BOnly S1
COnly S2
DBoth S1 and S2
Answer:(A) Neither S1 nor S2
Explanation
Grammar G is ambiguous because terminal string 'c' has two distinct leftmost derivations, preventing it from being parsed by any deterministic LL or LR parser.
For string 'c', two derivations exist:
S => A => c
S => B => c
Ambiguity introduces a FIRST/FIRST conflict in LL(1) parsers because FIRST(A) and FIRST(B) both contain terminal 'c'.
Ambiguity introduces a reduce/reduce conflict in LR(1) parsers when lookahead symbol is end-of-input ($), because the parser cannot decide whether to reduce to non-terminal A or B.
Because no ambiguous grammar can be LL(1) or LR(1), neither statement S1 nor S2 is correct (Option A).
Consider R to be any regular language and L1, L2 be any two context-free languages. Which one of the following is correct ?
AL1 – R is context free
B(L1 ∪ L2) – R is context free
CL1 ∩ L2 is context free
DL̅1 is context free
Answer:(A) L1 – R is context free
Explanation
The set difference of a context-free language and a regular language is always context-free because it is equivalent to intersecting a CFL with a regular language.
The set difference is expressed as L1 - R = L1 ∩ R', where R' is the complement of R.
Because regular languages are closed under complementation, R' is guaranteed to be regular.
Context-free languages are closed under intersection with regular languages (via product PDA-DFA construction).
Therefore, L1 ∩ R' is always context-free (Option A).
Context-free languages are not closed under intersection (Option C) or complementation (Option D).
Sign in to read the full explanation
Frequently asked questions
How many Theory of Computation and Compilers questions have been asked in UGC NET Computer Science?
167 Theory of Computation and Compilers questions appear in the UGC NET Computer Science papers held between 2018–2026, and all of them are on this page with their answer key.
Are the answers on this page free?
Yes. Every question, its options, and the correct answer are free to read with no account. Signing in additionally unlocks the detailed explanation under each question.
Is Theory of Computation and Compilers an important topic for UGC NET Computer Science?
Theory of Computation and Compilers appears in every recent UGC NET Computer Science paper, across all 14 sittings covered here. Its share of the paper makes it worth revising thoroughly rather than sampling.
How should I practise Theory of Computation and Compilers after reading these questions?
Attempt the Theory of Computation and Compilers topic-wise sets, which put the same questions into a timed interface with instant scoring and weak-area analysis afterwards.
