UGC NET CS Practice Set 6

Explanation: A deterministic Turing machine (DTM) is in exactly one configuration at each step — the transition function maps each (state, symbol) pair to exactly one (state, symbol, direction). A nondeterministic TM may branch into multiple configurations, but a standard DTM has a single execution path.

Explanation: The pumping lemma provides a necessary condition for regularity (or context-freeness). If a language violates the pumping lemma, it is NOT regular (or NOT context-free). However, satisfying the pumping lemma does NOT prove a language is regular — it is a one-directional tool.

Explanation: Three-address code can be implemented using quadruples (op, arg1, arg2, result), triples (op, arg1, arg2 — result is implicit), or indirect triples. All three are valid representations; the choice depends on the compiler's design.

Explanation: Loop unrolling replicates the loop body multiple times within a single iteration, reducing loop overhead (fewer branch instructions, increment/comparison operations). Moving loop-invariant code outside is 'code motion', a different optimization.

Explanation: The CFL pumping lemma states: for any CFL L, there exists n such that for any z ∈ L with |z| ≥ n, z = uvwxy where (1) |vx| ≥ 1, (2) |vwx| ≤ n, and (3) uvⁱwxⁱy ∈ L for all i ≥ 0. Both v and x are pumped together.

Explanation: To prove a problem is NP-hard, we show a polynomial-time many-one (Karp) reduction from a known NP-hard problem to it. If a known NP-complete problem (like SAT) can be reduced to problem X in polynomial time, then X is NP-hard.

Explanation: The Transport Layer (Layer 4) provides end-to-end communication services including reliable data transfer, error recovery (retransmission), flow control, and segmentation/reassembly. The Data Link Layer provides hop-to-hop error detection, not end-to-end.

Explanation: A Class B address starts with 10 in the first two bits, and uses 16 bits for the network ID and 16 bits for the host ID. This allows 2^14 = 16,384 networks (since 2 bits are the class identifier) with up to 65,534 hosts each.

Explanation: TCP connection establishment uses a three-way handshake: (1) Client sends SYN (with initial sequence number), (2) Server replies with SYN-ACK (acknowledging client's SYN, sending its own SYN), (3) Client sends ACK (acknowledging server's SYN). The connection is now established.

Explanation: With /26, the host portion is 32 − 26 = 6 bits. Total addresses per subnet = 2^6 = 64. Subtracting the network address and broadcast address: 64 − 2 = 62 usable host addresses.

Explanation: The Bellman-Ford (Distance Vector) algorithm exchanges distance vectors between neighbors. It can suffer from the count-to-infinity problem when a link fails, causing routing loops. Solutions include split horizon, poison reverse, and hold-down timers.

Explanation: DNS primarily uses UDP port 53 for standard queries (speed over reliability for small messages). TCP port 53 is used for zone transfers between DNS servers and when the response exceeds 512 bytes (or the EDNS0 buffer size).

Explanation: RSA's security relies on the computational difficulty of factoring n = p × q, the product of two large prime numbers. Given the public key (e, n), finding the private key d requires knowing φ(n) = (p−1)(q−1), which requires factoring n.

Explanation: ARP resolves IP addresses to MAC (hardware) addresses on a local network. When a host needs to send a frame to an IP address on its subnet, it broadcasts an ARP request; the owner of that IP replies with its MAC address.

Explanation: Nyquist's formula for a noiseless channel: Maximum data rate = 2B log₂(L) bps, where B is bandwidth in Hz and L is the number of discrete signal levels. Shannon's formula (B log₂(1+S/N)) applies to noisy channels.

Explanation: For a Go-Back-N protocol with window size W, we need the sequence number space ≥ W + 1, so at least 8 values → 3 bits (2^3 = 8 ≥ 7+1). For Selective Repeat, the requirement is sequence space ≥ 2W, which would need 4 bits.

Explanation: HTTPS uses TLS/SSL, which operates between the Application Layer and the Transport Layer. TLS provides encryption, authentication, and integrity. In the TCP/IP model, it sits on top of TCP and below application protocols like HTTP.

Explanation: A packet filter firewall examines each packet independently based on header fields (source/destination IP, port, protocol) without maintaining connection state. A stateful firewall tracks connection states. An application gateway operates at the application layer.

Explanation: Basic Diffie-Hellman does not authenticate the communicating parties, making it vulnerable to man-in-the-middle attacks. An attacker can intercept and establish separate shared secrets with each party. This is mitigated by using authenticated DH or digital signatures.

Explanation: In CSMA/CD (used in Ethernet), upon detecting a collision, the station sends a 48-bit jam signal to ensure all stations detect the collision, then waits a random time chosen by binary exponential backoff (0 to 2^k − 1 slot times, k = attempt number) before retransmitting.

Explanation: SMTP uses TCP port 25 for sending email between mail servers. Port 21 is FTP control, port 80 is HTTP, and port 443 is HTTPS. SMTP with TLS uses port 587 (submission) or 465 (SMTPS).

Explanation: The minimum IPv4 header size (without options) is 20 bytes (5 × 32-bit words). This includes version, IHL, total length, identification, flags, fragment offset, TTL, protocol, header checksum, source and destination IP addresses.

Explanation: SSH (Secure Shell) provides encrypted remote login, command execution, and file transfer. Telnet transmits data (including passwords) in plain text. SSH uses public-key cryptography for authentication and symmetric encryption for data transfer.

Explanation: Standard Ethernet has an MTU of 1500 bytes (the maximum payload size of an Ethernet frame). The total frame size is up to 1518 bytes (14 bytes header + 1500 bytes payload + 4 bytes FCS). Jumbo frames can have MTU up to 9000 bytes.

Explanation: In digital signatures, the sender signs (encrypts the hash of) the message with their private key. The receiver verifies the signature using the sender's public key. This provides authentication (proves the sender's identity) and non-repudiation.

Explanation: A* uses f(n) = g(n) + h(n), where g(n) is the actual cost from start to node n, and h(n) is the heuristic estimate from n to the goal. A* is optimal and complete when h(n) is admissible (never overestimates) and consistent.

Explanation: D-separation in Bayesian networks determines conditional independence. X and Y are d-separated given Z if every undirected path between them is blocked. A path is blocked if it contains a chain/fork node in Z, or a collider NOT in Z (and none of its descendants are in Z).

Explanation: Expert systems consist of a knowledge base (domain facts and rules, typically if-then rules) and an inference engine (forward/backward chaining). They can explain their reasoning chain (explanation facility), unlike black-box models.

Explanation: In fuzzy logic, a membership function maps each element to a degree of membership in the range [0, 1], where 0 means no membership and 1 means full membership. Values between 0 and 1 represent partial membership, unlike crisp (Boolean) logic.

Explanation: A single-layer perceptron can only learn linearly separable functions. AND and OR are linearly separable and can be learned. XOR is not linearly separable (proved by Minsky and Papert, 1969) and requires at least one hidden layer.