HPCL IS – Previous Year Questions 2022 | TVK-TheVictoryKey

To recognise {ww^R}, a machine must first push all characters of w onto a stack, then pop them while matching with w^R. But the midpoint of the string is unknown — the machine cannot deterministically decide when w ends and w^R begins. This inherent non-determinism means it can only be accepted by an NPDA, NOT a DPDA. Hence it is a CFL but NOT a DCFL.

• B & D — {bⁿabⁿ} and {aⁿbaⁿ}: The middle separator (a or b) is a unique sentinel. A DPDA pushes the first block, sees the separator, then pops while matching the second block — completely deterministic.
• C — {bⁿaⁿ}: Classic DCFL. Push b's, then pop one per a. No ambiguity.

DCFL ⊂ CFL. Every DCFL is a CFL, but not every CFL is a DCFL. Key non-DCFLs to remember: {ww^R}, {ww}, and languages that require "guessing" a midpoint. DCFLs are closed under complementation but NOT under union or intersection.

The language (ab)*a generates: a, aba, ababa, abababa, … Starting from S:

This correctly matches (ab)*a. Option A is also a right-linear grammar (non-terminal always at right end), making it a valid regular grammar.

• B — S → aS | b: Generates strings of a's ending in b (e.g., aab). Completely wrong language.
• C — S → abS | b: Terminal rule is b alone, so strings end in b. Not matching (ab)*a.
• D — S → bS | a: Generates b*a — strings of b's followed by a. Wrong language.

Primitive (atomic) regular expressions are defined as: ∅ (empty set), λ (empty string), and any single symbol from the alphabet (a, b, c, …). These are the base cases. (a + b)* is a compound expression built using union (+) and Kleene star (*) — it is NOT primitive.

Any regular expression that uses an operator (+ union, · concatenation, * Kleene star) is NOT primitive. It is a composed/derived expression.

The hierarchy: Regular ⊂ CFL ⊂ CSL ⊂ Recursively Enumerable. Since regular languages are a strict subset of CFLs, every regular language is also context-free.

• A: {aⁿbⁿ} is CFL but NOT regular (proved by Pumping Lemma). So not every CFL is regular.
• C: Completely false — CFLs are EXACTLY the languages recognised by Pushdown Automata (PDA).
• D: CFLs are NOT closed under intersection. Example: {aⁿbⁿc^m} ∩ {a^mbⁿcⁿ} = {aⁿbⁿcⁿ} which is NOT a CFL.

• Closed under: Union, Concatenation, Kleene star, Homomorphism
• NOT closed under: Intersection, Complementation

A regular grammar requires all productions to be either right-linear (A → aB or A → a) or left-linear (A → Ba or A → a). Option B satisfies this: S → aS (right-linear), S → a (terminal), A → bA (right-linear), A → b (terminal). All valid.

• A — A → bAc: Non-terminal A is in the MIDDLE, not at the right end. This makes it context-free, not regular.
• C — A → abAc: Multiple terminals before and after the non-terminal — not regular.
• D — A → bAc and A → abc: Same issue — non-terminal in the middle.

The DFA tracks |w| mod 3. State 1 = 0 mod 3 (start & accept), State 2 = 1 mod 3, State 3 = 2 mod 3. On every character read, we move to the next state cyclically:

Strings accepted: ε (length 0), aab (length 3), aaaaaa (length 6), etc.

• A: All states loop to themselves — every state accepts only if it's a final state. This DFA would accept ALL strings (or none), not just multiples of 3.
• C: δ(1,b)=1 means 'b' doesn't advance the counter — string "b" would be accepted at length 1 incorrectly.
• D: Jumps directly from state 1 to state 3 on first symbol — skips the "length 1" tracking entirely.

Pattern: the language consists of arbitrary arrangements of the "tokens" c and ab. So strings are built by choosing 'c' or 'ab' zero or more times:

• A — c*(a+b): Must end with a or b and cannot produce ε or cc.
• B — (b + ac)*: Tokens are b and ac — produces strings like b, ac, bac, etc. Not matching.
• D — (a + bc)*: Tokens are a and bc — produces a, bc, abc (=a+bc), etc. Generates "abc" differently and misses "ab".

All strings start with S → aaB. Then B → Aa → (bBb)a → … The grammar naturally generates strings of the form aa + (nested bBb expansions) + a chain. aabbabba cannot be derived because the structure of b-groups and a-sequences doesn't match the grammar's production pattern.

For CFG derivation questions, always start from S and apply productions systematically. Track what each derivation step produces and verify character by character.

The stack top symbol is crucial — the PDA's behaviour depends on what's currently on top of the stack, enabling it to match nested structures like parentheses or {aⁿbⁿ}.

Examples: "a" (0 b's, 1 a), "bba" (2 b's, 1 a), "bbaaa" (2 b's, 3 a's) — all match.

(i) TRUE: Γ is indeed the finite set of tape symbols, and Σ ⊆ Γ.

(ii) FALSE: The blank symbol b is in Γ (tape alphabet) but b ∉ Σ (input alphabet). This is a critical distinction — the blank b separates the input from unused tape cells, and it is never part of the input string itself.

In regex notation, '+' (or '|') means union/OR. So 'a + b' means "either a or b" — exactly the set {a, b}. Do not confuse '+' in regex with arithmetic addition or Kleene plus.

• A — {a,b}*: This would be (a+b)* — all strings including ε.
• D — {λ, a, b}: That would be (a+b+λ) or (a+b)? — includes empty string.

{a, b} is set notation, not regex notation. A regular expression uses symbols, operators (+, ·, *), and parentheses. Curly-brace set notation is from set theory / formal language description — it is not a valid regular expression syntax.

Statements B, C, D are all definitionally true for any DFA. Statement A says "F may be empty" — formally, F ⊆ Q and F = ∅ is allowed (DFA accepts nothing). However, many textbooks and exam setters consider a DFA with empty F as degenerate/invalid, making A "incorrect" from that perspective. This is the intended answer in the exam.

• δ: Q × Σ → Q is a total function (defined for every state-symbol pair) — this distinguishes DFA from NFA.
• Q must be non-empty (at least q₀ ∈ Q).
• q₀ ∈ Q by definition.

The ready queue contains the Process Control Blocks (PCBs) of all processes that are loaded in memory and waiting for CPU time. It must be in RAM for the CPU scheduler to access it rapidly. Secondary memory is too slow; tertiary is even slower.

• Job queue: All processes in system (may be on disk)
• Ready queue: In RAM — ready to execute
• Device queues: In RAM — waiting for I/O

A system call is the programmatic interface between a user-space application and OS kernel services. They are exposed as an API (e.g., POSIX in Unix). Examples: read(), write(), fork(), open(). When called, the CPU switches from user mode to kernel mode.

• Demand paging / Virtual memory / Segmentation are memory management techniques, not API mechanisms.

The long-term (job) scheduler selects which jobs from the job pool (disk) to bring into the ready queue (RAM). It controls the degree of multiprogramming. It is invoked infrequently.

• Long-term (Job) scheduler: Disk → Ready queue. Controls multiprogramming degree. Slow.
• Short-term (CPU) scheduler: Ready queue → CPU. Very fast. Runs every few milliseconds.
• Medium-term scheduler: Handles swapping — moves processes between RAM and disk to free memory.
• Dispatcher: Performs the actual context switch — loads registers, switches to user mode.

(i) TRUE: A process is a container for threads. A single process can have many threads (e.g., a browser has separate threads for UI, network, rendering).

(ii) TRUE: Threads are called "lightweight processes" because they share the parent process's memory space, code, and resources. Creating/switching threads is cheaper than full process creation.

• TAT = Completion Time − Arrival Time
• WT = TAT − Burst Time
• Response Time = Start Time − Arrival Time

The correct direction is: programs needed by the CPU are transferred FROM auxiliary memory (HDD/SSD) TO main memory (RAM), not the other way around. When a program is needed, the OS loads it into RAM for execution. Transferring to auxiliary memory is what happens during swapping (moving OUT of RAM).

A system call is the only safe, controlled mechanism for user-space programs to request kernel services. It triggers a CPU trap/interrupt to switch from user mode to kernel mode, execute the requested service, and return. CUI/GUI are user interfaces, not kernel access mechanisms.

TLB is a hardware cache that stores recent page-number → frame-number mappings. Without TLB, every memory access requires TWO memory lookups: one for the page table + one for the actual data. With TLB, if the mapping is cached (TLB hit), only one lookup is needed. TLB hit ratio is typically 95–99%.

This is also the number of edges in a complete graph K₁₀. Each of 10 nodes connects to 9 others, but each link is shared by 2 nodes.

55 = 10×11/2 = C(11,2). That's the formula with n=11, not n=10. A common trap.

TCP (Transmission Control Protocol) at the Transport layer provides: reliable delivery (ACKs + retransmissions), sequencing (sequence numbers), flow control (sliding window), and congestion control.

• Internet layer: IP is best-effort, connectionless — no guarantee of delivery or order.
• Physical layer: Deals with bits on wire — no error correction at this level.
• Application layer: Deals with application protocols (HTTP, SMTP) — not sequencing.

TELNET (TELecommunication NETwork) provides a virtual terminal protocol — it allows a user to log into a remote host and interact character-by-character or line-by-line. It uses port 23. Note: TELNET transmits data in plaintext — SSH is its secure replacement.

• FTP: File Transfer Protocol — for transferring files, not interactive terminal sessions.
• TFTP: Trivial FTP — simplified file transfer, no authentication.
• Anonymous FTP: FTP variant allowing login without credentials.

4096 is the total number of addresses. But the network address (all host bits = 0) and broadcast address (all host bits = 1) cannot be assigned to hosts. So usable = 4096 − 2 = 4094.

ICMP (Internet Control Message Protocol) is a network-layer protocol for error reporting and diagnostics. It reports both dropped packets (e.g., "Destination Unreachable") and connectivity failures (e.g., "Echo Request/Reply" used by ping). It does NOT deliver data — it only carries control messages.

• Type 0/8: Echo Reply/Request (ping)
• Type 3: Destination Unreachable (dropped packet)
• Type 11: Time Exceeded (TTL expired — used by traceroute)

RIP (Routing Information Protocol): Interior Gateway Protocol (IGP) using Distance Vector algorithm. Metric = hop count (max 15). Simple but slow convergence.

EGP (Exterior Gateway Protocol): Used for inter-domain routing between autonomous systems. Largely replaced by BGP today, but is still a valid routing protocol.

RARP (Reverse ARP) allows a device that knows only its MAC address to discover its IP address from a RARP server. It is the reverse of ARP (which maps IP → MAC).

RARP is largely obsolete, replaced by DHCP (Dynamic Host Configuration Protocol).

The Entity Integrity Constraint states: "No primary key attribute can be NULL." This ensures every entity (row) in a relation can be uniquely identified. A primary key with NULL would mean an entity that cannot be distinguished from others.

• Key constraint: States that primary key must be unique (no two rows same PK). Different from the NULL rule.
• Domain constraint: Restricts values an attribute can take (e.g., age must be positive integer).
• Foreign key constraint (Referential integrity): A foreign key value must match a PK in the referenced table or be NULL.

An identifying relationship (double diamond) connects a weak entity to its identifying (owner) entity. Without this relationship, the weak entity cannot be uniquely identified.

• Rectangle → Entity
• Double rectangle → Weak entity
• Diamond → Relationship
• Double diamond → Identifying relationship
• Ellipse → Attribute
• Dashed ellipse → Derived attribute
• Double ellipse → Multivalued attribute

SELECT and FROM are mandatory in a standard SQL query — they define what to retrieve and from where. WHERE is optional — omitting it retrieves all rows. A minimal valid query: SELECT * FROM Employee;

The selection (σ) operator in relational algebra filters rows based on a predicate. σ_condition(R) returns only the tuples from R that satisfy the condition. It is equivalent to SQL's WHERE clause: SELECT * FROM Employee WHERE Age < 20;

1NF ✓: Given — all attributes atomic and single-valued.

2NF ✓: Since A is a single-attribute key, there can be no partial dependency (partial dependency requires a composite key). So 2NF is always satisfied.

3NF — NOT guaranteed: If B → C exists and B is not a candidate key, there is a transitive dependency (A→B→C), violating 3NF. We don't know the FDs, so 3NF is not necessarily true.

BCNF — may or may not hold (same reasoning). This statement is trivially true as a "maybe" claim.

• 1NF: Atomic values, no repeating groups
• 2NF: 1NF + no partial dependencies on PK
• 3NF: 2NF + no transitive dependencies
• BCNF: Every determinant is a candidate key

Division R ÷ S ≠ S ÷ R in general — the schemas must be compatible in a specific direction. Union (A∪B=B∪A), Intersection (A∩B=B∩A), and Natural Join (R⋈S=S⋈R) are all commutative — order doesn't affect the result.

GRANT is a DCL (Data Control Language) command — it gives users permissions on database objects.

• DDL: CREATE, ALTER, DROP, TRUNCATE
• DML: SELECT, INSERT, UPDATE, DELETE
• TCL: COMMIT, ROLLBACK, SAVEPOINT
• DCL: GRANT, REVOKE

Matrix Chain Multiplication asks for the optimal parenthesisation of n matrices to minimise scalar multiplications. The DP solution fills an n×n table with O(n) work per cell → Θ(n³). The brute force approach (trying all parenthesisations) is exponential — Ω(2ⁿ). Neither n² nor n log n describes it.

In the 0-1 Knapsack, each item must be taken wholly or left entirely. A greedy choice (always pick highest value/weight ratio) may leave gaps that smaller items could fill more optimally. This requires Dynamic Programming for optimal solution.

Fractional Knapsack CAN be solved greedily — you can take fractions, so always picking highest ratio is always optimal.

• Greedy works: Fractional Knapsack, MST (Prim/Kruskal), Dijkstra's, Huffman Coding, Activity Selection
• DP needed: 0-1 Knapsack, Matrix Chain Multiplication, Longest Common Subsequence, Floyd-Warshall

DFS explores as deep as possible before backtracking — this LIFO (Last-In-First-Out) behaviour matches a stack. In recursive DFS, the call stack acts implicitly. Iterative DFS uses an explicit stack.

BFS (Breadth-First Search) uses a Queue (FIFO) to explore level-by-level. The Queue option is for BFS, not DFS — a common trap.

The merge() function merges two sorted subarrays of total size n by comparing elements one by one — it takes O(n) time. The O(log n) factor comes from the number of recursive levels (log n levels), and at each level, O(n) total work is done → overall O(n log n).

• Stable? Yes — equal elements maintain relative order
• In-place? No — needs O(n) extra space
• Best/Avg/Worst: All O(n log n)
• Best for linked lists (no extra space needed)

MCM cannot be solved optimally by greedy because the optimal parenthesisation depends on the combination of all dimensions — a local greedy choice may lead to globally suboptimal results. This is a classic DP problem. B, C, D are all correct facts.

Kruskal's MST algorithm sorts edges by weight and greedily adds the cheapest edge that does NOT form a cycle. To efficiently detect cycles, it uses a Disjoint Set (Union-Find) data structure. Time complexity with union by rank + path compression: O(E log E).

• Prim's: MST using priority queue / min-heap. Grows tree one vertex at a time.
• Dijkstra's: SSSP using priority queue/min-heap, not disjoint sets.
• Huffman: Uses a min-heap/priority queue to build optimal prefix codes.

By BST property: all left subtree keys < root < all right subtree keys. Inorder visits Left → Root → Right, which naturally outputs keys in sorted (non-decreasing) order. This is a fundamental BST property used for sorting.

• Inorder (L-R-T): Sorted output for BST
• Preorder (R-L-T): Used for copying trees, prefix expressions
• Postorder (L-T-R): Used for deleting trees, postfix expressions
• Level order (BFS): Level-by-level, uses queue

The 5 BSTs with {1,2,3}: root=1 (2 trees), root=2 (1 tree), root=3 (2 trees). Distinct BSTs ≠ distinct binary trees (which can have same shape but different keys).

• n=1: 1 BST
• n=2: 2 BSTs
• n=3: 5 BSTs
• n=4: 14 BSTs

Note: 7 (option A) = total nodes at heights 0+1+2 = 1+2+4 = 7, which is internal nodes only. Don't confuse total nodes (15) with leaf nodes (8).

After partition(), the pivot element is in its correct final sorted position — all elements to its left are smaller, all to its right are larger. This is Quick Sort's key invariant.

• B: Worst case is O(n²) — happens when pivot is always min/max (e.g., sorted array with last element as pivot). O(n log n) is average case.
• C: Quick Sort is NOT stable — elements with equal values may change relative order during partitioning.
• D: Space complexity is O(log n) for the recursion stack (average) — not O(n).

(i) TRUE: Strassen divides each n×n matrix into four n/2×n/2 submatrices and recursively computes 7 products (instead of 8 in naive divide-and-conquer).

(ii) TRUE: For 2×2 matrices: 7 multiplications + 18 additions/subtractions. Compare with naive: 8 multiplications + 4 additions. Strassen saves one multiplication at the cost of more additions.

In Register Addressing Mode, the operand resides in a CPU register, and the instruction's address field specifies which register (e.g., R1, R2). This is the fastest mode because no memory access is needed.

• Immediate: Operand is in the instruction itself (A → operand "in instruction" = option A)
• Direct: Instruction has the memory address → option C
• Register: Instruction has register name → option B ✓
• Indirect: Instruction has address of a memory word that holds the actual address
• Implied: Operand is implicit (e.g., stack top in zero-address)
• Relative: EA = PC + displacement

8 is log₂(256) — not relevant here. The trap is confusing page offset bits (9) with page number bits (3).

In three-address instructions, each of the three address fields can refer to either a register or a memory location — there's no requirement that the first address must always be a register. This is confirmed by option D (which is correct).

Zero-address instructions don't specify any operand address because the operand location is implied — it's always the top of the stack. E.g., ADD pops TOS and SOS, adds them, pushes result. The stack pointer implicitly defines operand locations.

(i) TRUE: The opcode (operation code) field specifies what operation to perform (ADD, MOV, SUB, etc.).

(ii) FALSE: The mode field specifies the addressing mode (how to interpret the address field) — NOT the actual address. The actual address is in the address field.

Once all k stages are occupied (pipeline full), one instruction exits (completes) every clock cycle — throughput = 1 instruction/cycle.

• A: First instruction takes k cycles to complete (goes through all k stages). Not 1 cycle.
• B: Throughput is 1/cycle (not 1/k cycles) once full. 1/k is the throughput of a NON-pipelined processor.
• D: Pipelining does NOT reduce individual instruction latency — each instruction still takes k cycles. It increases THROUGHPUT, not reduces latency.

(i) TRUE: Effective Address = Program Counter + displacement. The PC holds the address of the next instruction, and a displacement is added.

(ii) TRUE: The displacement (offset) can be positive (jump forward) or negative (jump backward). This is how loops in assembly work — a negative offset jumps back to the loop start.

One-address instructions use the Accumulator (AC) as an implicit second operand. ADD A adds the contents of memory location A to the accumulator and stores the result in AC. LOAD A copies M[A] into AC (not the other way).

• A: LOAD A means AC ← M[A] (load FROM memory INTO accumulator). Option A reverses this — that would be STORE A.
• B: Stack computers use zero-address instructions (operands implicitly on stack).
• C: Index Register is used in indexed addressing mode — not the default for one-address instructions.

Adding two n-bit numbers produces at most an (n+1)-bit sum. For n=3: output = 4 bits. The extra bit handles the carry-out.

(i) TRUE: A shift register is built from a chain of flip-flops (usually D flip-flops) clocked together, sometimes with additional logic gates for serial/parallel input-output.

(ii) TRUE: Shift registers can perform serial data transfer (SISO, SIPO, PISO, PIPO) and are used in serial communication, data conversion, and multiplication/division by 2.

This is the Complement Law: A + A' = 1. Either A is 1 (so A=1 makes it 1) or A' is 1 (when A=0, A'=1). One of them is always 1.

The two carry outputs from both half adders are ORed to get the final carry-out. An AND gate would be wrong — two carries can never both be 1 simultaneously (so OR and AND give same result, but conceptually it's OR).

• Half Subtractor: Difference = A⊕B (XOR), Borrow = A'·B (AND + NOT). Needs an additional NOT gate.
• Full Adder: Needs 2 XOR, 2 AND, 1 OR (or 2 half adders + 1 OR).
• Full Subtractor: Even more gates.

With 2 variables (A, B), there are 4 input combinations (00, 01, 10, 11). Each combination can output 0 or 1 independently → 2⁴ = 16 possible truth tables = 16 distinct Boolean functions.

These include: AND, OR, XOR, NAND, NOR, XNOR, NOT A, NOT B, A, B, 0, 1, etc.

y = 3 is invalid immediately — the digit '3' appears in (231)_y, and digits must be less than the base. So y > 3.

The binary number in the question may have a typo (the math for y=4 gives (231)₄ = 32+12+1 = 45 = (101101)₂, not (11101)₂). The most common exam answer is y = 4 as the smallest valid base greater than 3.

An empty condition in a for loop is treated as always true in C++. So for(int i=1; ; i++) never stops — it's an infinite loop.

for(int i=0; i==10; i++) — i starts at 0, condition i==10 is immediately FALSE (0≠10), so the loop body executes zero times and exits. Not infinite, but a zero-iteration loop.

Option D: starts at a=1, condition a<10 is true, then increments a before printing: prints 2, 3, 4, ..., 10. Misses 1! The condition also stops before a=10 can re-enter — wait, let's trace: when a=9, condition true, a becomes 10, prints 10. Then condition a<10 is false (10<10 = false), exits. Prints 2–10, missing 1.

The do-while: prints a=1, increments to 2, checks 2≤10 (true)... continues until printing 10, increments to 11, checks 11≤10 (false), stops. Prints 1–10 correctly ✓

Both parameters are strings: filename (path to file) and mode ("r", "w", "a", "rb", etc.). Return type is FILE*, not void.

In C, assigning 130 to a signed char causes implementation-defined behaviour (overflow), but on most systems with two's complement, the result is -126.

If char is unsigned (0 to 255), x=130 would print 130. If signed (-128 to 127), 130 overflows to -126. By default in most compilers, char is signed.

Cache is the fastest memory in the hierarchy, sitting between CPU registers and RAM. It stores frequently/recently accessed data so the CPU doesn't always have to access slow RAM.

FAT is a file system structure where each entry corresponds to a disk block (cluster). Each FAT entry contains either the next block in a file chain, or a special marker (EOF, free, bad). The FAT is indexed by block number, making it a disk-wide lookup table for block allocation.

• File transfer (FTP): Uses TCP (connection-oriented) — ensures complete, ordered file delivery ✓
• Remote login (Telnet/SSH): Uses TCP — interactive sessions need reliable, ordered delivery ✓
• PSTN (Public Switched Telephone Network): Circuit-switched — establishes a dedicated physical connection before communication ✓