UGC NET June 2004 - Computer Science Paper 2

A Finite State Machine (FSM) can be modeled as a Turing Machine with a finite tape length, no rewinding capability, and unidirectional tape movement (read-only).

Moore and Mealy machines are both finite state machines that produce output. It is a fundamental result in automata theory that Moore and Mealy machines are computationally equivalent, meaning any Moore machine can be converted to an equivalent Mealy machine and vice versa.

Finite State Machines (FSMs) are the least powerful class in the Chomsky hierarchy, specifically designed to recognize regular languages defined by regular grammars.

A Turing Machine (TM) has an infinite tape that allows it to read, write, and move in both directions, providing it with memory that is not limited by the number of states. FSMs have a fixed, finite amount of memory determined by their state count.

Non-deterministic finite state machines (NDFSM) and deterministic finite state machines (DFSM) are equivalent in terms of the class of languages they can recognize, which is the class of regular languages.

A command file, often referred to as a script or batch file, contains a sequence of commands that are executed by a computer program or shell.

An interpreter is a program that directly executes instructions written in a programming language, allowing for interactive feedback during the compilation or execution process.

Moore and Mealy machines are models for transducers, which map input strings to output strings. The length difference in output is a standard property of the Moore machine, which produces an output for every state transition including the initial state.

The Pumping Lemma is a proof technique used to show that a language is not regular by demonstrating that it fails the conditions required for regular languages.

For an alphabet of size 2 (0 and 1) and strings of length n, each position has 2 choices. Thus, there are 2 * 2 * ... * 2 (n times) = 2^n possible strings.

The fundamental constraint of an FSM is its finite memory, which prevents it from tracking information that grows with the size of the input string.

Given A*A = AA + A'A'. Since AA = A and A'A' = A', we get A + A'. By the law of excluded middle, A + A' = 1.

Gallium Arsenide (GaAs) is a semiconductor material known for high electron mobility, enabling very high-speed operation, though it is more difficult to manufacture than silicon-based components.

Recognizing palindromes requires comparing the first half of a string with the reversed second half, which necessitates storing the entire first half. An FSM lacks the memory to store strings of arbitrary length.

The pumping lemma relies on the fact that if a string is longer than the number of states in a DFA, the path must visit at least one state twice (the pigeonhole principle), creating a loop that can be repeated.

If C = AB + A'B', then C * A = (AB + A'B')A + (AB + A'B')'A'. This simplifies to (ABA + A'B'A) + (AB + A'B')'A'. Since ABA = AB and A'B'A = 0, the expression reduces to AB + (A' + B)(A + B')A'. This evaluates to B.

In formal language theory, the 'formal' aspect refers to the structure or syntax of the strings rather than the semantic meaning of the symbols themselves.

In a Moore machine, the output is determined solely by the current state. In a Mealy machine, the output depends on both the current state and the current input.

In computing, prefixes are powers of 2. Kilo = 2^10, Mega = 2^20, Giga = 2^30, and Tera = 2^40.

Test the options: For D (0, 0, 1): AB + A'C = (00) + (11) = 1 (True). AC + B = (0*1) + 0 = 0 (True). Both equations are satisfied.

In ASCII, uppercase letters (e.g., 'A' is 01000001) and lowercase letters (e.g., 'a' is 01100001) differ by the 6th bit (value 32 or 00100000). Setting this bit to 1 using an OR operation converts uppercase to lowercase.

EBCDIC (Extended Binary Coded Decimal Interchange Code) is an 8-bit character encoding, which allows for 2^8 = 256 distinct characters.

The hexadecimal number system uses base 16, utilizing digits 0-9 and letters A-F to represent values from 0 to 15.

ASCII (American Standard Code for Information Interchange) is the standard character encoding used for electronic communication between terminals and computers.

Quadratic probing uses the sequence (h(k) + i^2) mod m. Starting at 4 with m=8, the sequence is 4, (4+1) mod 8 = 5, (4+4) mod 8 = 0 (or 8 if 1-indexed), (4+9) mod 8 = 5, (4+16) mod 8 = 4. Since the probe sequence repeats, locations like 2, 3, 6, and 7 are never reached.

This is a variation of the birthday paradox. The probability of no collision for n items in m slots is (m/m) * ((m-1)/m) * ... * ((m-n+1)/m). For 10 records in 100 slots, the probability of no collision is approx 0.63, meaning the probability of at least one collision is 1 - 0.63 = 0.37, which is closest to 0.34.

In linear probing, the average number of probes increases significantly as the load factor approaches 1. Keeping the load factor low ensures fewer collisions and faster search times.

Stacks are LIFO structures used for expression evaluation, recursion, and syntax parsing. CPU scheduling typically uses queues (like round-robin) or priority queues, not stacks.

IPv4 addresses are 32 bits long, which is equivalent to 4 bytes.

Vinton Cerf and Robert Kahn are widely recognized as the fathers of the Internet for their work on the TCP/IP protocols.

IPv6 addresses are 128 bits long, which is equivalent to 16 bytes.

The Internet Protocol (IP) operates at the Network layer (Layer 3) of the OSI model.

FTP, HTTP, and SMTP are all application-layer protocols that rely on the transport layer (TCP/UDP) and the network layer (IP) to transmit data.

The address 127.0.0.1 is the standard IPv4 loopback address used for testing network connectivity on the local host.

The minimum size of an IPv4 header is 20 bytes, which occurs when no optional fields are included.

E-R modeling is a top-down approach because it starts by identifying high-level entities and relationships before defining specific attributes.

In standard E-R diagrams, rectangles represent entity sets, diamonds represent relationships, and ellipses represent attributes.

While E-R models can be mapped to various normal forms, the standard mapping procedure is generally designed to produce relations in 3NF to minimize redundancy.

The E-R model is classified as an object-based logical model because it describes data in terms of entities and relationships rather than tables or records.