Unit 8: Theory Of Computation and Compilers

THEORY OF COMPUTATION & COMPILERS

UGC NET / JRF — Computer Science & Applications

High-Yield Study Notes & PYQ-Pattern Workbook (Unit 8)

Contents

Ch.1 — Theory of Automata

Ch.2 — Regular Expressions

Ch.3 — Context Free Grammar (CFG)

Ch.4 — Pushdown Automata (PDA)

Ch.5 — Turing Machine

Ch.6 — Pumping Lemma

Ch.7 — What is a Compiler?

Ch.8 — Phases of Compiler

One-Shot Revision

Mini Mock Test (Answer Key)

Beginner → Concept → NET-level → JRF-level. Compact by design — exam value over page count.

Chapter 1 — Theory of Automata

1.1 Chomsky Hierarchy (Foundation)

Type	Language	Recognized by	Grammar restriction
Type 0	Recursively Enumerable	Turing Machine	No restriction (α→β)
Type 1	Context-Sensitive	Linear Bounded Automaton	|α|≤|β|
Type 2	Context-Free	Pushdown Automaton	A→β (single non-terminal LHS)
Type 3	Regular	Finite Automaton	A→aB or A→a

JRF trapThe Chomsky Hierarchy is STRICTLY nested: Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable. Every regular language is context-free, but NOT every context-free language is regular (e.g., {aⁿbⁿ} is context-free but not regular). This strict-subset relationship (and knowing a language that separates each pair, like aⁿbⁿ separating Type 3 from Type 2) is extremely frequently tested.

1.2 DFA (Deterministic Finite Automaton)

Formal definitionA DFA is a 5-tuple (Q, Σ, δ, q0, F): Q=finite set of states, Σ=input alphabet, δ=transition function (Q×Σ→Q, EXACTLY one transition per symbol per state), q0=start state, F=set of final/accepting states.

JRF trap — DFA vs NFA transition functionDFA's δ: Q×Σ→Q gives EXACTLY ONE next state (deterministic, total function — every state must have a transition defined for every symbol). NFA's δ: Q×Σ→P(Q) can give ZERO, ONE, or MULTIPLE next states (a set/subset of states), AND may include ε-transitions (moving states without consuming input). This exact difference in the transition function's codomain (Q vs P(Q)) is the core formal distinction tested.

1.3 NFA to DFA Conversion (Subset Construction)

JRF-level numerical — subset constructionNFA: states {A,B,C}, A is start, C is final. δ(A,0)={A,B}, δ(A,1)={A}, δ(B,1)={C}. Subset construction: Start state of DFA = {A}. On 0: {A}→{A,B}. On 1: {A}→{A}. From {A,B}: on 0→{A,B}(A goes to{A,B}, B has no 0-transition, so just {A,B}); on 1→{A,C}(A→{A}, B→{C}, union={A,C}). From {A,C}: on 0→{A,B} (C has no transitions, only A contributes); on 1→{A} (C has no 1-transition either). DFA states: {A}, {A,B}, {A,C} — with {A,C} being the ONLY accepting state (contains original final state C). This "build the DFA state-by-state, taking unions of NFA reachable states" technique is THE standard subset-construction JRF numerical.

NET pointIn the worst case, converting an n-state NFA to a DFA can require UP TO 2ⁿ DFA states (since each DFA state corresponds to a SUBSET of NFA states) — though in practice many fewer are typically reachable/needed.

1.4 DFA Minimization

IdeaMinimizing a DFA means merging EQUIVALENT states (states that behave identically for every possible future input) into single states, producing the smallest possible DFA that accepts the SAME language. Standard technique: start by partitioning states into {Final} and {Non-final}, then repeatedly refine partitions based on where each state's transitions lead, until no further refinement is possible.

1.5 Equivalence of DFA, NFA, and Regular Expressions

NET pointDFA, NFA (with or without ε-transitions), and Regular Expressions are all EQUIVALENT in expressive power — each can be converted to either of the others, and all three exactly capture the class of REGULAR LANGUAGES. This three-way equivalence (Kleene's theorem) is a foundational fact frequently tested as "which of these is NOT equivalent to a DFA" (trick: none — they all are).

MUST REMEMBER — Chapter 1

• Chomsky hierarchy (strict subsets): Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable.
• DFA: δ:Q×Σ→Q (exactly one transition, total function). NFA: δ:Q×Σ→P(Q) (zero/one/many transitions, may include ε).
• Subset construction converts NFA→DFA; worst case 2ⁿ DFA states for n NFA states.
• DFA minimization merges equivalent states via partition refinement.
• DFA ≡ NFA ≡ Regular Expressions in expressive power (all capture exactly Regular Languages).

DON'T CONFUSE

• DFA (exactly one transition per symbol) vs NFA (zero, one, or many transitions, plus possible ε-moves).
• DFA/NFA/Regex being EQUIVALENT in power vs being IDENTICAL in size/state-count (an NFA is often much smaller).

JRF CHALLENGE ZONE — Chapter 1

1. Which language separates Type 3 (Regular) from Type 2 (Context-Free) — i.e., is context-free but NOT regular? (a) a* (b) {aⁿbⁿ : n≥0} (c) (ab)* (d) Empty language
Answer: (b)

2. An NFA has 4 states. What is the MAXIMUM possible number of states in its equivalent DFA (subset construction, worst case)? (a) 4 (b) 8 (c) 16 (d) 2
Answer: (c) — 2⁴=16.

3. Which of these is NOT equivalent in expressive power to a DFA? (a) NFA (b) NFA with ε-transitions (c) Regular Expression (d) None — all are equivalent
Answer: (d)

Practice Questions — Chapter 1 (7)

1. List the 4 levels of the Chomsky Hierarchy from most to least restrictive.
   Ans: Regular (Type 3), Context-Free (Type 2), Context-Sensitive (Type 1), Recursively Enumerable (Type 0)
2. What are the 5 components of a DFA's formal definition?
   Ans: Q (states), Σ (alphabet), δ (transition function), q0 (start state), F (final states)
3. What is the key difference between a DFA's and an NFA's transition function?
   Ans: DFA's δ gives exactly one next state; NFA's δ can give zero, one, or many next states (a subset), and may include ε-transitions
4. In the worst case, how many DFA states can an n-state NFA require after subset construction?
   Ans: Up to 2ⁿ
5. What is the goal of DFA minimization?
   Ans: To merge equivalent states, producing the smallest DFA accepting the same language
6. Are DFA, NFA, and Regular Expressions equally powerful?
   Ans: Yes — all three exactly capture the class of regular languages (Kleene's theorem)
7. Give an example of a language that is context-free but not regular.
   Ans: {aⁿbⁿ : n≥0}

---

Chapter 2 — Regular Expressions

2.1 Regular Expression Operators

Operator	Meaning
Union (+, or |)	Either of two patterns (r1+r2 means r1 OR r2)
Concatenation (·)	One pattern followed by another (r1r2)
Kleene Star (*)	ZERO or more repetitions
Kleene Plus (+, superscript)	ONE or more repetitions (r+ = rr*)

JRF trap — Kleene star includes the empty stringr* ALWAYS includes ε (the empty string) — even if r itself does not match ε — because "zero repetitions" is a valid interpretation. Students often forget that a* includes ε. In contrast, r+ (one or more) does NOT necessarily include ε unless r itself can match ε.

2.2 Regular Expression to NFA (Thompson's Construction)

IdeaThompson's Construction builds an NFA piece-by-piece, following the regex's structure: a base symbol becomes a simple 2-state NFA; union creates a new start state branching (via ε) to both sub-NFAs; concatenation joins one sub-NFA's accept state to the next's start (via ε); Kleene star adds ε-loops allowing the sub-NFA to repeat zero or more times.

2.3 Closure Properties of Regular Languages

Operation	Closed?
Union	Yes
Concatenation	Yes
Kleene Star	Yes
Complement	Yes
Intersection	Yes

JRF trapRegular languages are closed under ALL the standard operations (union, concatenation, star, complement, intersection, difference) — a very "clean"/robust class. Context-Free Languages, in contrast, are NOT closed under intersection or complement (though they ARE closed under union, concatenation, and star) — this exact "CFLs are NOT closed under intersection/complement, but Regular languages ARE" contrast is a favourite JRF trap.

2.4 Pigeonhole Principle & Regular Language Limits

IdeaA finite automaton has a FIXED, finite number of states. By the pigeonhole principle, processing a sufficiently long string forces the automaton to REVISIT some state (a "cycle"/loop must occur) — this is the foundational insight behind the Pumping Lemma (Chapter 6), and explains WHY regular languages can't "count" arbitrarily high (like matching aⁿbⁿ for any n).

MUST REMEMBER — Chapter 2

• r* always includes ε (zero repetitions); r+ doesn't necessarily include ε.
• Thompson's Construction: regex→NFA, built recursively following the regex's structure using ε-transitions.
• Regular languages ARE closed under: union, concatenation, star, complement, intersection, difference.
• Context-Free languages are NOT closed under intersection or complement (but ARE closed under union, concatenation, star).
• Finite automaton's fixed state count + pigeonhole principle → cannot "count" unboundedly → basis of Pumping Lemma.

DON'T CONFUSE

• Regular languages (closed under intersection/complement) vs Context-Free languages (NOT closed under intersection/complement).
• Kleene Star r* (includes ε always) vs Kleene Plus r+ (includes ε only if r does).

JRF CHALLENGE ZONE — Chapter 2

1. Which class of languages is NOT closed under intersection? (a) Regular (b) Context-Free (c) Both are closed (d) Neither is closed
Answer: (b)

2. Does a* include the empty string ε, even if 'a' itself is just a single character?
Answer: Yes — Kleene star always includes zero repetitions (ε).

Practice Questions — Chapter 2 (6)

1. Does r* always include the empty string ε?
   Ans: Yes, always (zero repetitions)
2. Does r+ always include ε?
   Ans: No, only if r itself can already match ε
3. What does Thompson's Construction do?
   Ans: Converts a regular expression into an equivalent NFA, built recursively using ε-transitions
4. List two operations under which Regular languages are closed.
   Ans: Any two of: union, concatenation, Kleene star, complement, intersection, difference
5. Are Context-Free Languages closed under intersection?
   Ans: No
6. What foundational principle explains why a finite automaton cannot "count" arbitrarily high?
   Ans: The pigeonhole principle — a fixed number of states forces a cycle/repeat on sufficiently long input

---

Chapter 3 — Context Free Grammar (CFG)

3.1 CFG — Formal Definition

Formal definitionA CFG is a 4-tuple (V, Σ, R, S): V=set of non-terminals (variables), Σ=set of terminals, R=set of production rules (each of the form A→β, where A is a SINGLE non-terminal and β is any string of terminals/non-terminals), S=start symbol.

3.2 Derivations & Parse Trees

Derivation Type	Idea
Leftmost Derivation	At each step, expand the LEFTMOST non-terminal
Rightmost Derivation	At each step, expand the RIGHTMOST non-terminal

JRF insightLeftmost and Rightmost derivations of the SAME string may apply the SAME production rules but in a DIFFERENT ORDER — yet both correspond to the exact SAME parse tree (parse trees capture structure, not derivation order). This "different derivation order, same tree" distinction is frequently tested.

3.3 Ambiguity in CFGs

IdeaA CFG is AMBIGUOUS if some string in its language has MORE THAN ONE distinct parse tree (equivalently, more than one leftmost derivation). Ambiguity is often problematic for compilers, since it means a program's meaning could be interpreted in multiple structurally different ways.

JRF-level example — classic ambiguous grammarGrammar: E→E+E | E*E | id. The string "id+id*id" has TWO different parse trees depending on whether + or * is grouped first (since the grammar gives no precedence information) — this is the textbook example of CFG ambiguity, fixed by rewriting the grammar to enforce precedence (E→E+T|T; T→T*F|F; F→id).

NET pointAmbiguity is a property of a GRAMMAR, not fundamentally of the LANGUAGE itself — some INHERENTLY ambiguous languages exist where EVERY possible grammar for that language must be ambiguous, but for many ambiguous grammars, an EQUIVALENT unambiguous grammar CAN be found (as in the E+E/E*E example above).

3.4 Chomsky Normal Form (CNF) & Greibach Normal Form (GNF)

Normal Form	Production rule shape
CNF	A→BC (two non-terminals) OR A→a (single terminal) — nothing else allowed (except possibly S→ε for the start symbol)
GNF	A→aα (a single terminal FOLLOWED BY zero or more non-terminals)

JRF trapEvery Context-Free Grammar can be converted into an EQUIVALENT grammar in CNF or GNF (same language, different rule shape) — this conversion is always POSSIBLE, a frequently tested fact. CNF is specifically useful because it makes parsing algorithms like CYK run in predictable polynomial time (using exactly 2 symbols per production simplifies the DP table structure).

MUST REMEMBER — Chapter 3

• CFG = (V, Σ, R, S); every rule has a SINGLE non-terminal on the left side.
• Leftmost/Rightmost derivations can differ in order but represent the SAME parse tree.
• A grammar is ambiguous if some string has more than one parse tree; classic example: E→E+E|E*E|id.
• Ambiguity is a grammar property — some (but not all) ambiguous grammars have an equivalent unambiguous grammar; some languages are INHERENTLY ambiguous.
• CNF: A→BC or A→a. GNF: A→aα. Every CFG can be converted to CNF or GNF.

DON'T CONFUSE

• Ambiguous grammar (fixable by rewriting) vs Inherently ambiguous language (no grammar can avoid ambiguity).
• CNF (A→BC or A→a) vs GNF (A→aα, terminal always first).

JRF CHALLENGE ZONE — Chapter 3

1. The grammar E→E+E|E*E|id generating "id+id*id" is: (a) Unambiguous, one parse tree (b) Ambiguous, two parse trees (c) Not a valid CFG (d) Only valid for regular languages
Answer: (b)

2. In Chomsky Normal Form, a production A→BC means: (a) A single terminal (b) Exactly two non-terminals on the right (c) A terminal followed by a non-terminal (d) An empty production
Answer: (b)

Practice Questions — Chapter 3 (7)

1. What are the 4 components of a CFG's formal definition?
   Ans: V (non-terminals), Σ (terminals), R (production rules), S (start symbol)
2. Differentiate leftmost and rightmost derivation.
   Ans: Leftmost expands the leftmost non-terminal at each step; rightmost expands the rightmost non-terminal at each step
3. When is a CFG called ambiguous?
   Ans: When some string in its language has more than one distinct parse tree
4. Give the classic example of an ambiguous grammar.
   Ans: E→E+E | E*E | id (no precedence enforced)
5. Is ambiguity always fixable by rewriting the grammar?
   Ans: No — some languages are inherently ambiguous, where every possible grammar for them is ambiguous
6. What is the production rule shape in Chomsky Normal Form?
   Ans: A→BC (two non-terminals) or A→a (single terminal)
7. Can every CFG be converted into CNF?
   Ans: Yes, always, into an equivalent grammar generating the same language

---

Chapter 4 — Pushdown Automata (PDA)

4.1 PDA — Formal Definition

SimpleA PDA is a Finite Automaton PLUS a STACK (unbounded auxiliary memory) — the stack lets it "remember" unboundedly much information, which is exactly what's needed to recognize Context-Free Languages (like matching aⁿbⁿ, which a plain DFA/NFA cannot do).

Formal definitionA PDA is a 7-tuple (Q, Σ, Γ, δ, q0, Z0, F): Q=states, Σ=input alphabet, Γ=STACK alphabet, δ=transition function (depends on current state, input symbol (or ε), AND stack top), q0=start state, Z0=initial stack symbol, F=final states.

4.2 PDA ↔ CFG Equivalence

NET pointPDAs and CFGs are EXACTLY EQUIVALENT in expressive power — every CFG can be converted to an equivalent PDA, and every PDA's language can be described by some CFG. Both exactly capture the class of CONTEXT-FREE LANGUAGES. This equivalence (analogous to DFA≡NFA≡Regex for regular languages) is a foundational, frequently tested fact.

4.3 Deterministic PDA (DPDA) vs Non-deterministic PDA (NPDA)

JRF trap — DPDA is STRICTLY weaker than NPDAUnlike the DFA/NFA case (where determinism doesn't reduce expressive power), a Deterministic PDA is STRICTLY LESS POWERFUL than a Non-deterministic PDA — there exist context-free languages (e.g., EVEN-LENGTH PALINDROMES) that CANNOT be recognized by ANY deterministic PDA, but CAN be recognized by a non-deterministic one. This "DPDA ⊊ NPDA in power" fact (unlike DFA≡NFA) is one of the most important and frequently tested distinctions in this chapter.

4.4 Acceptance by Final State vs Empty Stack

Method	Idea
Final State	String accepted if the PDA ends in a designated FINAL state (stack contents at that point don't matter)
Empty Stack	String accepted if the PDA's stack becomes COMPLETELY EMPTY (regardless of which state it's in)

NET pointBoth acceptance methods (Final State, Empty Stack) are EQUIVALENT in power — any PDA using one method can be converted to an equivalent PDA using the other, and both accept exactly the Context-Free Languages.

MUST REMEMBER — Chapter 4

• PDA = Finite Automaton + Stack (unbounded memory) → recognizes Context-Free Languages.
• PDA formal definition: (Q,Σ,Γ,δ,q0,Z0,F) — note the extra stack alphabet Γ and initial stack symbol Z0.
• PDA ≡ CFG in expressive power (both exactly capture Context-Free Languages).
• DPDA is STRICTLY WEAKER than NPDA (unlike DFA≡NFA) — some CFLs (e.g., even-length palindromes) need non-determinism.
• Final-state and Empty-stack acceptance are equally powerful (interconvertible).

DON'T CONFUSE

• DFA≡NFA (equal power) vs DPDA⊊NPDA (deterministic PDA is STRICTLY weaker) — a very common trap since students assume the DFA/NFA pattern always holds.

JRF CHALLENGE ZONE — Chapter 4

1. Which is TRUE about DPDA vs NPDA? (a) They are equally powerful, like DFA and NFA (b) DPDA is strictly weaker than NPDA (c) NPDA is strictly weaker than DPDA (d) Neither can recognize any CFL
Answer: (b)

2. What extra component does a PDA have compared to a plain Finite Automaton?
Answer: A stack (unbounded auxiliary memory)

Practice Questions — Chapter 4 (6)

1. What extra memory structure does a PDA have beyond a finite automaton?
   Ans: A stack
2. What class of languages does a PDA recognize?
   Ans: Context-Free Languages
3. List the 7 components of a PDA's formal definition.
   Ans: Q, Σ, Γ, δ, q0, Z0, F
4. Is a Deterministic PDA as powerful as a Non-deterministic PDA?
   Ans: No — DPDA is strictly weaker; some CFLs require non-determinism
5. Give an example of a language that needs a non-deterministic PDA (cannot be done deterministically).
   Ans: Even-length palindromes
6. Name the two standard PDA acceptance methods.
   Ans: Acceptance by final state, and acceptance by empty stack

---

Chapter 5 — Turing Machine

5.1 Turing Machine — Formal Definition

SimpleA Turing Machine (TM) is the most powerful model of computation in this hierarchy — it has an INFINITE tape (unlike a PDA's stack, which can only be accessed LIFO-style) that can be read AND written, with a head that can move LEFT or RIGHT.

Formal definitionA TM is a 7-tuple (Q, Σ, Γ, δ, q0, B, F): Q=states, Σ=input alphabet, Γ=tape alphabet (Σ⊆Γ), δ=transition function (Q×Γ→Q×Γ×{L,R} — reads a symbol, writes a symbol, moves left/right), q0=start state, B=blank symbol, F=final states.

5.2 Turing Machine vs PDA vs FA — Memory Comparison

Model	Memory	Recognizes
Finite Automaton	None (just states)	Regular Languages
Pushdown Automaton	Stack (LIFO only)	Context-Free Languages
Turing Machine	Infinite tape (read/write, both directions)	Recursively Enumerable Languages

JRF trap — read/write vs read-only, and direction of accessA PDA's stack is READ/WRITE but only accessible in LIFO order (top only) — you cannot read/modify the middle of the stack. A TM's tape is READ/WRITE and accessible in ANY ORDER (the head can move back and forth freely, revisiting and overwriting any cell) — this unrestricted random-access read/write capability is exactly what gives TMs their extra power over PDAs.

5.3 Church-Turing Thesis

IdeaThe Church-Turing Thesis states that ANY function that is "effectively computable" (computable by some intuitive algorithmic procedure) CAN be computed by a Turing Machine. This is a THESIS (a claim/hypothesis about the nature of computation), NOT a formally provable mathematical theorem — since "effectively computable" isn't itself a rigorously defined mathematical concept, only an intuitive one.

5.4 Decidability & the Halting Problem

Term	Meaning
Decidable	A TM exists that ALWAYS halts (accepts or rejects) for every input — an algorithm exists
Undecidable	NO TM exists that always halts correctly for every input
Recursively Enumerable (RE)	A TM exists that halts and ACCEPTS every string IN the language, but may loop forever on strings NOT in the language

JRF trap — the Halting Problem is undecidableThe Halting Problem ("given a program and input, will it eventually halt?") is the classic example of an UNDECIDABLE problem — proven via a diagonalization argument (assuming a "halts" decider exists leads to a logical contradiction). This is THE most famous undecidability result and is very frequently referenced/tested, often alongside "is this problem decidable or undecidable" scenario questions modeled after it.

NET pointA language is DECIDABLE if and only if BOTH it AND its complement are Recursively Enumerable (RE). If a language is RE but its complement is NOT RE, the language is RE but NOT decidable (the Halting Problem itself is exactly this case: RE but not decidable).

5.5 Variants of Turing Machines

Variant	Idea
Multi-tape TM	Multiple tapes/heads operating in parallel
Non-deterministic TM (NTM)	Multiple possible transitions from a state/symbol combination
Universal TM (UTM)	A single TM that can SIMULATE any other TM, given its description as input — the theoretical basis for general-purpose (stored-program) computers

NET pointMulti-tape TMs and Non-deterministic TMs are NOT more powerful than a standard single-tape deterministic TM in terms of WHAT they can compute (same class of languages) — they can only offer a SPEED advantage (polynomial-time simulation exists to convert them back to a standard single-tape TM). This "equivalent power, not equivalent speed" distinction is a frequently tested TM variant fact.

MUST REMEMBER — Chapter 5

• TM = infinite tape, read/write, head moves both directions — most powerful model, recognizes Recursively Enumerable languages.
• PDA's stack: read/write but LIFO-only access. TM's tape: read/write, any-order access (this is the source of TM's extra power).
• Church-Turing Thesis: a THESIS (not a provable theorem) — every effectively computable function is TM-computable.
• Decidable = TM always halts (accept/reject) for every input. Undecidable = no such TM exists.
• Halting Problem is THE classic undecidable problem.
• Decidable ⟺ language AND its complement are both RE.
• Multi-tape TM and NTM: same computational POWER as standard TM, only a potential SPEED difference.

DON'T CONFUSE

• Decidable (always halts, both accept/reject) vs Recursively Enumerable (halts+accepts for YES instances, may loop forever for NO instances).
• PDA's LIFO-only stack access vs TM's free/random tape access — this IS the source of TM's extra power.
• Church-Turing Thesis (unprovable claim) vs a mathematical theorem (provable).

JRF CHALLENGE ZONE — Chapter 5

1. The Halting Problem is: (a) Decidable (b) Undecidable (c) Not even Recursively Enumerable (d) Solvable with a PDA
Answer: (b)

2. A language is decidable if and only if: (a) It is RE only (b) Its complement is RE only (c) Both it and its complement are RE (d) Neither it nor its complement is RE
Answer: (c)

3. Compared to a standard single-tape deterministic TM, a multi-tape TM offers: (a) More computational power (can compute things a standard TM cannot) (b) The same power, only potentially faster (c) Less power (d) No relationship exists
Answer: (b)

Practice Questions — Chapter 5 (8)

1. What extra capability does a TM's tape have compared to a PDA's stack?
   Ans: The TM's tape allows read/write access in any order (head moves both directions); the PDA's stack only allows LIFO (top-only) access
2. What class of languages does a Turing Machine recognize?
   Ans: Recursively Enumerable Languages
3. Is the Church-Turing Thesis a provable mathematical theorem?
   Ans: No — it is a thesis/hypothesis, not formally provable, since "effectively computable" is an intuitive, not rigorous, concept
4. Define "decidable" for a language/problem.
   Ans: A TM exists that always halts (accepting or rejecting) for every input
5. What is the classic example of an undecidable problem?
   Ans: The Halting Problem
6. State the relationship between decidability and Recursive Enumerability of a language and its complement.
   Ans: A language is decidable if and only if both it and its complement are Recursively Enumerable
7. What is a Universal Turing Machine?
   Ans: A single TM that can simulate any other TM, given that TM's description as input
8. Do multi-tape and non-deterministic TMs compute a strictly larger class of languages than a standard TM?
   Ans: No — they have the same computational power, only a potential speed advantage

---

Chapter 6 — Pumping Lemma

6.1 Pumping Lemma for Regular Languages

StatementFor any regular language L, there exists a "pumping length" p such that every string w∈L with |w|≥p can be split as w=xyz, satisfying ALL THREE conditions: (1) |xy|≤p, (2) |y|≥1 (y is non-empty), (3) for ALL i≥0, xyⁱz ∈ L (pumping y any number of times, including zero, keeps the string in L).

JRF-level numerical — proving a language is NOT regularProve L={aⁿbⁿ : n≥0} is NOT regular using Pumping Lemma (proof by contradiction). Assume L IS regular, with pumping length p. Choose w=a^p b^p (valid, since |w|=2p≥p). By the lemma, w=xyz with |xy|≤p, |y|≥1. Since |xy|≤p, the substring xy consists ENTIRELY of a's (as the first p characters of w are all a's). So y = a^k for some k≥1. Now pump with i=2: xy²z = a^(p+k) b^p — this has MORE a's than b's (since k≥1), so xy²z ∉ L. This CONTRADICTS the pumping lemma's requirement that xyⁱz∈L for ALL i≥0. Contradiction → our assumption was false → L is NOT regular. This exact "choose w, use |xy|≤p to force y into a specific portion of the string, then pump to break membership" technique is THE standard Pumping Lemma proof structure for JRF/NET.

Trap — choosing the right stringThe choice of w matters enormously — a poorly chosen w might NOT lead to a contradiction even for a non-regular language (because the lemma only guarantees SOME split works, not that YOUR chosen split immediately breaks). The key trick is almost always choosing w so that the |xy|≤p constraint FORCES y to fall within a specific "countable" portion (like the a's block) of the string, leaving no room to pump without breaking the pattern.

6.2 Pumping Lemma for Context-Free Languages

StatementFor any CFL L, there exists p such that every string w∈L with |w|≥p can be split as w=uvxyz, satisfying: (1) |vxy|≤p, (2) |vy|≥1 (at least one of v,y is non-empty), (3) for ALL i≥0, uvⁱxyⁱz ∈ L.

JRF trap — CFL pumping lemma pumps TWO pieces togetherThe CFL version pumps v AND y SIMULTANEOUSLY (both must be repeated the SAME number of times, i) — unlike the regular-language version which only pumps ONE piece (y). This is used to prove languages like L={aⁿbⁿcⁿ : n≥0} are NOT context-free (even though {aⁿbⁿ} IS context-free) — since with only two "moving" pieces (v and y) available, you cannot keep three independent counts (a's, b's, c's) synchronized while pumping. Confusing the CFL pumping lemma's TWO-piece structure with the regular language version's ONE-piece structure is a common JRF error.

MUST REMEMBER — Chapter 6

• Regular PL: w=xyz, |xy|≤p, |y|≥1, xyⁱz∈L for all i≥0 (pumps ONE piece, y).
• CFL PL: w=uvxyz, |vxy|≤p, |vy|≥1, uvⁱxyⁱz∈L for all i≥0 (pumps TWO pieces, v and y, together).
• Standard proof structure: assume L IS regular/CFL, choose a clever w, use the length constraint to pin down where y (or v,y) must fall, then pump to derive a contradiction.
• {aⁿbⁿ} is context-free but not regular; {aⁿbⁿcⁿ} is not even context-free (needs 3 synchronized counts, but PL only pumps 2 pieces).

DON'T CONFUSE

• Regular Pumping Lemma (one piece, y) vs CFL Pumping Lemma (two pieces, v and y, pumped together).
• Pumping Lemma is used to PROVE a language is NOT in a class — it is NOT used to prove a language IS regular/context-free (satisfying the lemma doesn't guarantee membership).

JRF CHALLENGE ZONE — Chapter 6

1. In the Regular Pumping Lemma, which condition ensures y falls within the FIRST p characters of w? (a) |y|≥1 (b) |xy|≤p (c) xyⁱz∈L (d) None of these
Answer: (b)

2. Why can't {aⁿbⁿcⁿ} be proven context-free using a similar trick to {aⁿbⁿ}? (a) It actually IS context-free (b) The CFL pumping lemma only pumps 2 pieces, insufficient to keep 3 counts synchronized (c) CFLs cannot contain the symbol c (d) No reason, it's just conventionally excluded
Answer: (b)

3. Can the Pumping Lemma be used to PROVE a language IS regular?
Answer: No — it can only be used to prove a language is NOT regular (via contradiction); satisfying the lemma's conditions doesn't guarantee regularity.

Practice Questions — Chapter 6 (6)

1. State the three conditions of the Regular Pumping Lemma.
   Ans: |xy|≤p, |y|≥1, and xyⁱz∈L for all i≥0
2. What proof technique is standard for using the Pumping Lemma (regular or CFL)?
   Ans: Proof by contradiction — assume the language IS regular/CFL, choose a string, and pump to derive a contradiction
3. Prove {aⁿbⁿ} is not regular — what string w is typically chosen, and why?
   Ans: w = a^p b^p; the |xy|≤p condition forces y to be entirely a's, so pumping breaks the equal-count pattern
4. How many pieces does the CFL Pumping Lemma pump (compared to the Regular Pumping Lemma's one piece)?
   Ans: Two pieces (v and y), pumped together the same number of times
5. Can the Pumping Lemma be used to prove a language IS regular or context-free?
   Ans: No — it can only prove a language is NOT regular/context-free
6. Why is {aⁿbⁿcⁿ} not context-free, using the CFL Pumping Lemma intuition?
   Ans: With only two pumpable pieces available, it's impossible to keep three independent symbol counts (a's, b's, c's) synchronized while pumping

---

Chapter 7 — What is a Compiler?

7.1 Compiler — Definition

SimpleA compiler is a program that translates source code written in a HIGH-LEVEL language into an equivalent program in a LOWER-LEVEL language (typically machine code or assembly), performing the ENTIRE translation before execution begins.

7.2 Types of Translators

Translator	Idea
Compiler	Translates the ENTIRE source program upfront, produces a separate executable, then runs
Interpreter	Translates and EXECUTES source code line-by-line/statement-by-statement, no separate executable produced
Assembler	Translates assembly language (low-level mnemonics) into machine code
Cross-Compiler	Runs on one platform (host) but generates code for a DIFFERENT target platform
Just-In-Time (JIT) Compiler	Compiles code to machine code AT RUNTIME, just before execution — combines aspects of both interpretation and compilation (e.g., used in Java's JVM, modern JavaScript engines)

JRF trapA JIT compiler is NEITHER a pure compiler NOR a pure interpreter — it typically starts by interpreting/executing bytecode, then COMPILES "hot" (frequently executed) code paths to native machine code at runtime for a speed boost, blending both approaches. This hybrid nature is frequently tested as "which category does JIT belong to."

7.3 Bootstrapping (Compiler Self-Hosting)

IdeaBootstrapping is the process of writing a compiler for a language IN THAT SAME LANGUAGE — first written in another language (or by hand), then progressively used to compile improved/full versions of itself. This is how many modern compilers (e.g., GCC) are built and maintained.

MUST REMEMBER — Chapter 7

• Compiler: translates whole program upfront, produces separate executable, then runs.
• Interpreter: translates+executes line-by-line, no separate executable.
• Cross-compiler: runs on one platform, generates code for a DIFFERENT target platform.
• JIT compiler: hybrid — interprets bytecode, compiles "hot" paths to native code at runtime.
• Bootstrapping: writing a compiler for a language IN that same language.

DON'T CONFUSE

• Compiler (translate all, then run) vs Interpreter (translate+run line-by-line) vs JIT (hybrid, compiles hot paths at runtime).
• Cross-compiler (different TARGET platform) vs a regular compiler (same platform as host).

JRF CHALLENGE ZONE — Chapter 7

1. A JIT compiler is best described as: (a) A pure compiler only (b) A pure interpreter only (c) A hybrid that interprets and compiles hot paths at runtime (d) Neither a compiler nor interpreter
Answer: (c)

2. A compiler that runs on a Windows PC but generates machine code for an embedded ARM device is called a: (a) Cross-compiler (b) Interpreter (c) Assembler (d) Bootstrapper
Answer: (a)

Practice Questions — Chapter 7 (5)

1. What is the key difference between a compiler and an interpreter?
   Ans: A compiler translates the whole program before execution, producing a separate executable; an interpreter translates and executes line-by-line, with no separate executable
2. What does a cross-compiler do differently from a regular compiler?
   Ans: It runs on one platform but generates code for a different target platform
3. Why is a JIT compiler considered a hybrid approach?
   Ans: It typically interprets bytecode initially, then compiles frequently-executed ("hot") code to native machine code at runtime
4. What does "bootstrapping" mean in the context of compilers?
   Ans: Writing a compiler for a language using that same language
5. What does an assembler translate?
   Ans: Assembly language (low-level mnemonics) into machine code

---

Chapter 8 — Phases of Compiler

8.1 The Compiler Phases (Pipeline)

Source Code → Lexical Analysis (produces Tokens) → Syntax Analysis (produces Parse Tree / AST) → Semantic Analysis (produces Annotated AST, type-checked) → Intermediate Code Generation → Code Optimization → Code Generation → Target Machine Code [Symbol Table Management + Error Handling run alongside ALL phases]

8.2 Lexical Analysis (Scanning)

IdeaReads the raw source code character-by-character and groups them into TOKENS (meaningful units: keywords, identifiers, operators, literals) — implemented as a Finite Automaton (this is exactly WHERE Theory of Automata connects directly to compiler construction). Removes whitespace/comments.

JRF trap — lexical error examplesLexical analysis catches errors like an ILL-FORMED token (e.g., an identifier starting with a digit, like "2abc", or an unterminated string literal) — errors in the very SHAPE/spelling of a token, detected via the FA's transition rules. It does NOT catch grammar/structure errors (mismatched parentheses — that's Syntax Analysis) or meaning errors (type mismatches — that's Semantic Analysis).

8.3 Syntax Analysis (Parsing)

IdeaTakes the token stream and checks it against the language's GRAMMAR (typically a CFG), building a Parse Tree / Abstract Syntax Tree (AST) — this is exactly WHERE Context-Free Grammars (Chapter 3) connect directly to compilers.

Parser Type	Idea
Top-Down	Builds the parse tree from the ROOT downward (e.g., Recursive Descent, LL parsers)
Bottom-Up	Builds the parse tree from the LEAVES upward toward the root (e.g., LR, SLR, LALR parsers — generally MORE POWERFUL, can handle a broader class of grammars)

JRF trapLL parsers (top-down) read input Left-to-right, produce a Leftmost derivation. LR parsers (bottom-up) read input Left-to-right, produce a Rightmost derivation (in REVERSE, as it builds bottom-up). LR parsers can handle a STRICTLY LARGER class of grammars than LL parsers — this "LR is more powerful than LL" fact (and knowing LL=leftmost, LR=rightmost-in-reverse) is a very frequently tested parser-comparison question.

8.4 Semantic Analysis

IdeaChecks the MEANING of the syntactically-correct program — type checking, scope resolution (is a variable declared before use?), ensuring operations are applied to compatible types. Catches errors like "adding a string to an integer" or "using an undeclared variable" — these are grammatically valid but semantically wrong.

8.5 Intermediate Code Generation & Optimization

IdeaIntermediate Code (e.g., Three-Address Code, or an intermediate representation like LLVM IR) is a machine-independent representation — this allows the SAME front-end (lexer/parser/semantic analyzer) to be reused across DIFFERENT target machines, and the SAME back-end (code generation) to be reused across DIFFERENT source languages, by just swapping out the piece that connects to the intermediate representation. Code Optimization then improves this intermediate code (e.g., removing dead code, common sub-expression elimination) WITHOUT changing its meaning/output.

8.6 Code Generation & Symbol Table

IdeaCode Generation converts the (optimized) intermediate code into actual TARGET machine code (or assembly), handling register allocation and instruction selection. The Symbol Table is a data structure that stores information about identifiers (variables, functions) — name, type, scope, memory location — accessed and updated by EVERY phase of the compiler (not just one specific phase).

MUST REMEMBER — Chapter 8

• Phase order: Lexical → Syntax → Semantic → Intermediate Code → Optimization → Code Generation.
• Symbol Table and Error Handling run alongside ALL phases, not just one.
• Lexical Analysis = tokenizing, implemented as a Finite Automaton (catches ill-formed tokens).
• Syntax Analysis = parsing against a CFG, builds parse tree/AST (catches grammar/structure errors).
• LL parsers (top-down) = leftmost derivation; LR parsers (bottom-up) = rightmost derivation in reverse; LR is strictly MORE powerful than LL.
• Semantic Analysis catches meaning errors (type mismatches, undeclared variables) — grammatically valid but wrong.
• Intermediate code = machine-independent, enables front-end/back-end reuse across languages/targets.

DON'T CONFUSE

• Lexical errors (malformed tokens) vs Syntax errors (grammar structure) vs Semantic errors (meaning/types).
• LL parsing (top-down, leftmost) vs LR parsing (bottom-up, rightmost-in-reverse, more powerful).

JRF CHALLENGE ZONE — Chapter 8

1. Which compiler phase is implemented using Finite Automata theory? (a) Syntax Analysis (b) Lexical Analysis (c) Semantic Analysis (d) Code Generation
Answer: (b)

2. Which parser type is generally MORE powerful (handles a broader grammar class)? (a) LL (top-down) (b) LR (bottom-up) (c) Both are identical in power (d) Neither can handle CFGs
Answer: (b)

3. "Using a variable of type int as if it were a string" is caught at which phase? (a) Lexical (b) Syntax (c) Semantic (d) Code Generation
Answer: (c)

Practice Questions — Chapter 8 (8)

1. List the six main phases of a compiler in order.
   Ans: Lexical Analysis, Syntax Analysis, Semantic Analysis, Intermediate Code Generation, Code Optimization, Code Generation
2. What does the Lexical Analysis phase produce?
   Ans: A stream of tokens
3. What underlying theory (from this unit) is Lexical Analysis based on?
   Ans: Finite Automata (Theory of Automata)
4. What underlying theory is Syntax Analysis based on?
   Ans: Context-Free Grammars
5. Differentiate LL and LR parsers.
   Ans: LL is top-down, produces a leftmost derivation; LR is bottom-up, produces a rightmost derivation in reverse, and is more powerful
6. What kind of errors does Semantic Analysis catch?
   Ans: Meaning-based errors like type mismatches and undeclared variable usage — grammatically valid but semantically wrong
7. Why is machine-independent intermediate code useful in compiler design?
   Ans: It allows the front-end and back-end to be reused across different source languages and target machines
8. Is the Symbol Table used by only one specific compiler phase?
   Ans: No — it is accessed and updated across all phases of the compiler

---

One-Shot Revision — Unit 8

Key facts across all chapters

• Chomsky Hierarchy (strict subsets): Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable.
• DFA: δ:Q×Σ→Q (one transition). NFA: δ:Q×Σ→P(Q) (many/zero, +ε). Subset construction: NFA→DFA, worst case 2ⁿ states. DFA≡NFA≡Regex.
• Kleene star r* always includes ε; r+ doesn't necessarily. Regular languages closed under ALL standard ops; CFLs NOT closed under intersection/complement.
• CFG=(V,Σ,R,S), single non-terminal LHS. Ambiguous grammar = some string has >1 parse tree (e.g., E→E+E|E*E|id). CNF: A→BC or A→a.
• PDA = FA + stack (LIFO), recognizes CFLs. PDA≡CFG. DPDA is STRICTLY weaker than NPDA (unlike DFA≡NFA!).
• TM = infinite tape, read/write, any-direction access → recognizes Recursively Enumerable languages. Church-Turing Thesis = unprovable claim, not a theorem.
• Decidable = TM always halts. Halting Problem = classic undecidable problem. Decidable ⟺ language AND complement both RE.
• Multi-tape/NTM = same power as standard TM, only speed difference.
• Regular Pumping Lemma: pumps ONE piece (y), |xy|≤p,|y|≥1. CFL Pumping Lemma: pumps TWO pieces (v,y) together, |vxy|≤p,|vy|≥1. PL only proves NON-membership, never membership.
• Compiler=translate all upfront; Interpreter=line-by-line; JIT=hybrid (interpret+compile hot paths). Cross-compiler=different target platform. Bootstrapping=compiler written in its own language.
• Compiler phases: Lexical(FA-based,tokens)→Syntax(CFG-based,parse tree)→Semantic(type-check)→Intermediate Code→Optimization→Code Generation. Symbol table spans ALL phases.
• LL parsing=top-down,leftmost derivation. LR parsing=bottom-up,rightmost derivation(reverse),MORE powerful than LL.

Potential future exam areasPotential high-value exam area based on syllabus importance and historical question patterns: NFA-to-DFA subset construction numericals; Pumping Lemma proof-writing questions (choosing the right string and deriving the contradiction); CFG ambiguity identification and CNF conversion; DPDA-vs-NPDA power distinction questions; decidability/Halting-Problem scenario questions; and compiler-phase error-classification questions (lexical vs syntax vs semantic).

---

Unit 8 — UGC NET/JRF Mini Mock Test

45 questions across all 8 chapters. NTA/UGC NET-style question patterns — mixed NET/JRF difficulty, numerical, statement-based, matching and scenario-based. Answer key with brief explanations follows each question.

Q1. The Chomsky Hierarchy nesting order (most to least restrictive) is: (a) RE⊂CS⊂CF⊂Regular (b) Regular⊂CF⊂CS⊂RE (c) CF⊂Regular⊂CS⊂RE (d) All four are equal in power
Ans: (b) [Ch1 | NET]

Q2. A DFA's transition function δ has type: (a) Q×Σ→P(Q) (b) Q×Σ→Q (c) P(Q)×Σ→Q (d) Q×P(Σ)→Q
Ans: (b) [Ch1 | NET]

Q3. An NFA has 5 states. What is the maximum number of DFA states after subset construction?
Ans: 2⁵ = 32 [Ch1 | NET numerical]

Q4. Which of these is TRUE? (a) DFA is more powerful than NFA (b) NFA is more powerful than DFA (c) DFA and NFA are equally powerful (d) Neither can recognize any language
Ans: (c) [Ch1 | NET]

Q5. Does a* always include the empty string?
Ans: Yes [Ch2 | NET]

Q6. Which is NOT a closure property of Context-Free Languages? (a) Union (b) Concatenation (c) Kleene Star (d) Intersection
Ans: (d) [Ch2 | JRF]

Q7. Regular languages ARE closed under which of these? (a) Union only (b) Intersection only (c) Complement only (d) All of union, intersection, complement, concatenation, star
Ans: (d) [Ch2 | NET]

Q8. What are the 4 components of a CFG?
Ans: V (non-terminals), Σ (terminals), R (production rules), S (start symbol) [Ch3 | NET]

Q9. The grammar E→E+E|E*E|id is: (a) Always unambiguous (b) Ambiguous (c) Not a valid CFG (d) Equivalent to a regular expression
Ans: (b) [Ch3 | NET]

Q10. In Chomsky Normal Form, valid productions are of the form: (a) A→BCD (b) A→BC or A→a (c) A→aA (d) A→ABC
Ans: (b) [Ch3 | NET]

Q11. Is every ambiguous grammar's language inherently ambiguous (no unambiguous grammar possible)?
Ans: No — some ambiguous grammars have an equivalent unambiguous grammar; only some languages are inherently ambiguous. [Ch3 | JRF]

Q12. A PDA's memory structure is: (a) An infinite tape (b) A stack (c) A queue (d) None, it has no memory
Ans: (b) [Ch4 | NET]

Q13. PDAs are equivalent in power to which grammar type?
Ans: Context-Free Grammars [Ch4 | NET]

Q14. Is a Deterministic PDA as powerful as a Non-deterministic PDA? (a) Yes, always (b) No, DPDA is strictly weaker (c) No, NPDA is strictly weaker (d) They recognize entirely unrelated languages
Ans: (b) [Ch4 | JRF]

Q15. Give an example of a CFL that requires a non-deterministic PDA.
Ans: Even-length palindromes [Ch4 | JRF]

Q16. A Turing Machine's tape, compared to a PDA's stack, allows: (a) Only LIFO access (b) Read/write access in any order, both directions (c) Read-only access (d) No access at all
Ans: (b) [Ch5 | NET]

Q17. The Church-Turing Thesis is: (a) A formally proven theorem (b) An unprovable thesis/claim (c) A disproven conjecture (d) A property of regular languages only
Ans: (b) [Ch5 | NET]

Q18. The Halting Problem is: (a) Decidable (b) Undecidable (c) Regular (d) Context-free
Ans: (b) [Ch5 | NET]

Q19. A language is decidable if and only if: (a) It is RE (b) Its complement is RE (c) Both it and its complement are RE (d) Neither is RE
Ans: (c) [Ch5 | JRF]

Q20. Does a multi-tape TM compute a strictly larger class of languages than a single-tape TM?
Ans: No — same power, only a potential speed advantage. [Ch5 | NET]

Q21. In the Regular Pumping Lemma, the condition |xy|≤p is used to: (a) Ensure y is non-empty (b) Force y to fall within the first p characters of w (c) Guarantee the language is finite (d) Prevent pumping entirely
Ans: (b) [Ch6 | JRF]

Q22. How many pieces does the CFL Pumping Lemma pump together?
Ans: Two (v and y) [Ch6 | NET]

Q23. Can the Pumping Lemma prove a language IS regular?
Ans: No — only that it is NOT regular. [Ch6 | NET]

Q24. Which language is used as the classic example to prove non-regularity via Pumping Lemma?
Ans: {aⁿbⁿ : n≥0} [Ch6 | NET]

Q25. Why is {aⁿbⁿcⁿ} not context-free?
Ans: The CFL pumping lemma only pumps two pieces, insufficient to keep three counts synchronized [Ch6 | JRF]

Q26. A compiler, compared to an interpreter: (a) Executes line-by-line (b) Translates the whole program before execution (c) Never produces an executable (d) Is always slower at runtime
Ans: (b) [Ch7 | NET]

Q27. A JIT compiler is best described as: (a) Pure compiler (b) Pure interpreter (c) A hybrid of interpretation and runtime compilation (d) An assembler variant
Ans: (c) [Ch7 | NET]

Q28. A cross-compiler generates code for: (a) The same platform it runs on (b) A different target platform (c) No specific platform (d) Only assembly language
Ans: (b) [Ch7 | NET]

Q29. What does "bootstrapping" mean for a compiler?
Ans: Writing a compiler for a language in that same language [Ch7 | NET]

Q30. Which compiler phase produces tokens?
Ans: Lexical Analysis [Ch8 | NET]

Q31. Lexical Analysis is theoretically based on: (a) Context-Free Grammars (b) Finite Automata (c) Turing Machines (d) Pumping Lemma
Ans: (b) [Ch8 | NET]

Q32. Syntax Analysis is theoretically based on: (a) Finite Automata (b) Context-Free Grammars (c) Regular Expressions only (d) Turing Machines
Ans: (b) [Ch8 | NET]

Q33. "Using an undeclared variable" in otherwise valid code is caught at: (a) Lexical Analysis (b) Syntax Analysis (c) Semantic Analysis (d) Code Generation
Ans: (c) [Ch8 | NET]

Q34. Which parser type produces a leftmost derivation? (a) LL (top-down) (b) LR (bottom-up) (c) Both equally (d) Neither
Ans: (a) [Ch8 | NET]

Q35. Which parser type is generally MORE powerful, handling a broader class of grammars? (a) LL (b) LR (c) They are identical in power (d) Neither can parse CFGs
Ans: (b) [Ch8 | JRF]

Q36. Is the Symbol Table used only during Semantic Analysis?
Ans: No — it is accessed/updated across all compiler phases. [Ch8 | NET]

Q37. Why is intermediate code useful in compiler design?
Ans: It's machine-independent, allowing front-end and back-end reuse across languages/targets [Ch8 | NET]

Q38. Which is the correct compiler phase order? (a) Syntax→Lexical→Semantic (b) Lexical→Syntax→Semantic (c) Semantic→Syntax→Lexical (d) Lexical→Semantic→Syntax
Ans: (b) [Ch8 | NET]

Q39. An NFA has δ(A,0)={A,B}, δ(A,1)={A}, with A as start state. What is the DFA start state after subset construction?
Ans: {A} [Ch1 | JRF numerical]

Q40. Which of these correctly separates Type 3 from Type 2 in the Chomsky Hierarchy? (a) a* (b) {aⁿbⁿ} (c) Σ* (d) ∅
Ans: (b) [Ch1 | NET]

Q41. In GNF, every production has the form: (a) A→BC (b) A→aα (terminal first, then non-terminals) (c) A→α (any string) (d) A→ε only
Ans: (b) [Ch3 | NET]

Q42. Which acceptance method for a PDA requires the stack to be completely empty?
Ans: Empty stack acceptance [Ch4 | NET]

Q43. Is Recursively Enumerable (RE) the same as Decidable?
Ans: No — RE only guarantees halting/accepting for YES instances; Decidable requires halting for ALL inputs (both YES and NO). [Ch5 | JRF]

Q44. Which pumping lemma condition ensures at least one of the pumped pieces is non-empty, in the CFL version?
Ans: |vy|≥1 [Ch6 | NET]

Q45. Which of these is FALSE? (a) Every regular language is context-free (b) Every context-free language is regular (c) {aⁿbⁿ} is context-free (d) {aⁿbⁿ} is not regular
Ans: (b) — the reverse is not true; context-free is a strictly larger class. [Ch1 | JRF]

— End of Mock Test — Cross-check your score, revisit the "Don't Confuse" and "JRF Challenge Zone" boxes for any topic you missed, then re-attempt after 48 hours. —

Share: