GATE CSE 2008

Statement P: A function is continuous if its graph can be drawn without lifting the pen. The graph of $f(x)=|x|$ has no breaks or jumps, including at $x=0$.
We evaluate the limit at $x=0$: $\lim_{x \to 0^-} |x| = \lim_{x \to 0^-} (-x) = 0$ and $\lim_{x \to 0^+} |x| = \lim_{x \to 0^+} x = 0$. Since $f(0)=0$, $\lim_{x \to 0} f(x) = f(0)$. Thus, $f(x)$ is continuous for all real $x$. P is TRUE.

Statement Q: A function is differentiable at a point if its graph has a unique tangent line at that point. At $x=0$, the graph of $f(x)=|x|$ has a sharp corner (a "cusp").
The left-hand derivative at $x=0$ is $\lim_{h \to 0^-} \frac{|0+h|-|0|}{h} = \lim_{h \to 0^-} \frac{-h}{h} = -1$.
The right-hand derivative at $x=0$ is $\lim_{h \to 0^+} \frac{|0+h|-|0|}{h} = \lim_{h \to 0^+} \frac{h}{h} = 1$.
Since the left-hand derivative ($\ne -1$) and right-hand derivative ($\ne 1$) are not equal, $f(x)$ is not differentiable at $x=0$. Thus, $f(x)$ is not differentiable for all real values of $x$. Q is FALSE.

Therefore, P is true and Q is false.

Let S be a set with $n$ elements.
The largest equivalence relation on S is the universal relation, $R_L = \{(a,b) \mid a,b \in S\}$. Every element is related to every other element. The number of ordered pairs in $R_L$ is $n \times n = n^2$.
The smallest equivalence relation on S is the identity relation, $R_S = \{(a,a) \mid a \in S\}$. Each element is only related to itself. The number of ordered pairs in $R_S$ is $n$.
Therefore, the number of ordered pairs in the largest and the smallest equivalence relations are $n^2$ and $n$, respectively.

For $n$ Boolean variables, there are $2^n$ distinct possible input combinations.
For each of these $2^n$ input combinations, a Boolean function can independently output either 0 or 1.
Thus, for each input combination, there are 2 possible output values.
Since there are $2^n$ input combinations, and each can have 2 independent output choices, the total number of different Boolean functions is:
$\underbrace{2 \times 2 \times \dots \times 2}_{2^n \text{ \times }} = 2^{2^n}$

The minimum non-planar graphs are subdivisions of $K_5$ or $K_{3,3}$ (by Kuratowski's Theorem).
$K_5$ is the complete graph on 5 vertices.
$V(K_5) = 5$
The number of edges in $K_5$ is given by:
$E(K_5) = \binom{5}{2} = \frac{5 \times 4}{2} = 10$
$K_{3,3}$ is the complete bipartite graph with 3 vertices in each partition.
$V(K_{3,3}) = 3 + 3 = 6$
The number of edges in $K_{3,3}$ is given by:
$E(K_{3,3}) = 3 \times 3 = 9$
Comparing the number of edges, $K_{3,3}$ has 9 edges, which is less than $K_5$'s 10 edges. Thus, $K_{3,3}$ is the non-planar graph with the minimum possible number of edges.
Therefore, G has 9 edges and 6 vertices.

A topological ordering requires that for every directed edge $u \to v$, vertex $u$ appears before vertex $v$ in the ordering. Let's check option D.

The given DAG has edges including $1 \to 2$ and $1 \to 3$.
For option D: $3 \ 2 \ 4 \ 1 \ 6 \ 5$

1. For the edge $1 \to 2$, vertex $1$ must appear before vertex $2$. In option D, $2$ appears before $1$.
2. For the edge $1 \to 3$, vertex $1$ must appear before vertex $3$. In option D, $3$ appears before $1$.
   Since both conditions are violated, this ordering is not a topological ordering.

The membership problem for CFGs, the finiteness problem for FSAs, and the equivalence problem for FSAs are all decidable. Algorithms exist to determine whether a string is in a CFG's language, if an FSA's language is finite, or if two FSAs recognize the same language. However, there is no algorithm that can determine for an arbitrary CFG whether it is ambiguous. This property makes the ambiguity problem for CFGs undecidable.

Any finite language is regular, as it can be recognized by a finite automaton with a path for each string.
A. Every subset of a regular set is regular. False. Example: $\Sigma^*$ is regular, but $\{a^n b^n | n \ge 0\} \subset \Sigma^*$ is not regular.
B. Every finite subset of a non-regular set is regular. True. Any finite language is regular.
C. The union of two non-regular sets is not regular. False. Let $L_1 = \{a^n b^n | n \ge 0\}$ and $L_2 = \Sigma^* \setminus L_1$. Both $L_1$ and $L_2$ are non-regular. However, $L_1 \cup L_2 = \Sigma^*$, which is regular.
D. Infinite union of finite sets is regular. False. Example: $L = \bigcup_{n=0}^{\infty } \{a^n b^n\}$ is an infinite union of finite sets, but $L$ is non-regular.

A 6-to-64 line decoder requires 6 input bits. We can split these into two groups: 3 higher-order bits and 3 lower-order bits.

1. The 3 lower-order input bits ($A_2, A_1, A_0$) are fed to the data inputs of eight 3-to-8 decoders. These eight decoders produce the 64 output lines ($8 \times 8 = 64$).
2. The 3 higher-order input bits ($A_5, A_4, A_3$) are used to enable one of these eight decoders at a time. This requires an additional 3-to-8 decoder acting as an enable decoder.
3. The 8 outputs of this master 3-to-8 decoder are connected to the enable inputs of the eight slave 3-to-8 decoders.

Therefore, $8$ (for outputs) $+ 1$ (for enabling) $= 9$ decoders are needed.

The total number of decoders needed is $8+1=9$.

The given Boolean function is $f(w, x, y, z) = \Sigma (1,3,4,6,9,11,12,14)$.
We convert the minterms to binary and place them in a 4-variable K-map:

$m1 = 0001$
$m3 = 0011$
$m4 = 0100$
$m6 = 0110$
$m9 = 1001$
$m11 = 1011$
$m12 = 1100$
$m14 = 1110$

The K-map is as follows (rows are $wx$, columns are $yz$):

We form two groups of four 1's:

1. The corner group of four: $m1(0001), m3(0011), m9(1001), m11(1011)$.
   Comparing these minterms: $w$ changes (0 to 1), $x$ is 0, $y$ changes (0 to 1), $z$ is 1.
   This group simplifies to $x'z$.

2. The corner group of four: $m4(0100), m6(0110), m12(1100), m14(1110)$.
   Comparing these minterms: $w$ changes (0 to 1), $x$ is 1, $y$ changes (0 to 1), $z$ is 0.
   This group simplifies to $xz'$.

The simplified Boolean function is $f(w, x, y, z) = x'z + xz'$.
This expression can also be written as $x \oplus z$.
The variables $w$ and $y$ are not present in the simplified function.
Therefore, the function is independent of two variables ($w$ and $y$).

The address is divided into three fields: TAG, SET (or LINE), and WORD (or Block Offset).

1. WORD (Block Offset) bits: The line size is 64 words.
   $\text{WORD bits} = \log_2(\text{Line Size}) = \log_2(64) = 6 \text{ bits}$

2. SET (LINE) bits: The cache has 128 lines and is 4-way set associative.
   $\text{Number of Sets} = \frac{\text{Total Lines}}{\text{Associativity}} = \frac{128}{4} = 32$
   $\text{SET bits} = \log_2(\text{Number of Sets}) = \log_2(32) = 5 \text{ bits}$

3. TAG bits: The total CPU address is 20 bits.
   $\text{TAG bits} = \text{Total Address bits} - \text{SET bits} - \text{WORD bits}$
   $\text{TAG bits} = 20 - 5 - 6 = 9 \text{ bits}$
   Thus, the TAG, LINE, and WORD bits are 9, 5, and 6, respectively.

The total capacity is calculated by multiplying the number of surfaces, tracks per surface, sectors per track, and bytes per sector.
$\text{Capacity} = 16 \times 128 \times 256 \times 512 \text{ bytes} = 2^4 \times 2^7 \times 2^8 \times 2^9 \text{ bytes} = 2^{28} \text{ bytes}$
Since $1 \text{ Mbyte} = 2^{20} \text{ bytes}$, the capacity is $2^{28} / 2^{20} = 2^8 \text{ Mbyte} = 256 \text{ Mbyte}$.

To specify a particular sector, we need bits for the surface, track, and sector number.
Number of bits for surface = $\lceil \log_2(16) \rceil = 4$ bits.
Number of bits for track = $\lceil \log_2(128) \rceil = 7$ bits.
Number of bits for sector = $\lceil \log_2(256) \rceil = 8$ bits.
Total bits required = $4 + 7 + 8 = 19$ bits.

To maximize the number of nodes for a given height $h$, the binary tree must be a perfect binary tree, meaning all levels are completely filled.
The root is at level 0 and has $2^0 = 1$ node.
Level 1 has $2^1 = 2$ nodes.
Level 2 has $2^2 = 4$ nodes.
...
Level $k$ has $2^k$ nodes.
For a tree of height $h$, the levels range from 0 to $h$.
The total maximum number of nodes is the sum of nodes at each level:
$N = \sum_{k=0}^{h} 2^k$
This is a geometric series sum:
$N = 2^0 + 2^1 + \dots + 2^h = \frac{2^{h+1}-1}{2-1} = 2^{h+1}-1$

The number of distinct binary trees that can be formed with $n$ unlabeled nodes is given by the $n$-th Catalan number, $C_n$.
The formula for the $n$-th Catalan number is:
$C_n = \frac{1}{n+1} \binom{2n}{n}$
For three unlabeled nodes, $n=3$. Substituting $n=3$ into the formula:
$C_3 = \frac{1}{3+1} \binom{2 \times 3}{3} = \frac{1}{4} \binom{6}{3}$
Calculate the binomial coefficient:
$\binom{6}{3} = \frac{6!}{3!(6-3)!} = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$
Substitute the value back into the formula for $C_3$:
$C_3 = \frac{1}{4} \times 20 = 5$
Thus, 5 distinct binary trees can be formed with three unlabeled nodes.

Let's compare the worst-case time complexities of the given sorting algorithms:

• Merge Sort: $O(n \log n)$
• Bubble Sort: $O(n^2)$
• Quick Sort: $O(n^2)$ (occurs with already sorted or reverse-sorted input)
• Selection Sort: $O(n^2)$

Comparing these complexities, $O(n \log n)$ is asymptotically lower than $O(n^2)$. Therefore, Merge Sort has the lowest worst-case complexity.

The variable j starts at $1$ and doubles in each iteration, taking values $1, 2, 4, \dots, 2^k, \dots$.
The loop continues as long as the condition $j \le n$ is true. We are counting the number of times this comparison evaluates to true.
The values of j for which the condition $j \le n$ is true are $2^0, 2^1, 2^2, \ldots, 2^k$, where $2^k$ is the largest power of $2$ such that $2^k \le n$.
Taking $\log_2$ on both sides of $2^k \le n$, we get $k \le \log_2 n$.
Since $k$ must be an integer (representing the exponent of $2$), the maximum value for $k$ is $\lfloor \log_2 n \rfloor$.
Therefore, the comparisons that evaluate to true occur for $j = 2^0, 2^1, \ldots, 2^{\lfloor \log_2 n \rfloor}$.
The count of these values is $(\lfloor \log_2 n \rfloor - 0) + 1 = \lfloor \log_2 n \rfloor + 1$.

Here's the matching of CPU scheduling algorithms to their applications:

• (P) Gang Scheduling involves scheduling a group of related processes or threads to run simultaneously on different processors. Therefore, P matches (3) Thread Scheduling.
• (Q) Rate Monotonic Scheduling is a priority-based algorithm widely used in real-time scheduling systems where tasks have deadlines. Therefore, Q matches (2) Real-time Scheduling.
• (R) Fair Share Scheduling ensures that each user or group receives a guaranteed share of the CPU's processing time. Therefore, R matches (1) Guaranteed Scheduling.

Thus, the correct matching is P - 3, Q - 2, R - 1.

Statement A is true because kernel threads require a kernel mode switch and OS intervention for context switching, which is more overhead than user-level thread switching that happens entirely in user space. Statement B is true as user-level threads are managed by a user-level library without direct kernel involvement or specialized hardware. Statement C is true because the kernel schedules kernel threads, allowing it to distribute them across multiple processors. Statement D is false because if one kernel-level thread blocks (e.g., waiting for I/O), the kernel can still schedule other kernel-level threads from the same process to run, preventing the entire process from blocking.

The final answer is $\boxed{D}$

Top-down parsers build the parse tree from the root (start symbol) down to the leaves (input tokens) by predicting the next production rule.
A recursive descent parser is a type of top-down parser that consists of a set of recursive procedures, one for each non-terminal, which directly implement the grammar's production rules.
Conversely, operator precedence, LR(k), and LALR(k) parsers are all types of bottom-up parsers, which build the parse tree from the leaves up to the root.

In Manchester encoding, each bit is represented by two signal transitions (e.g., a high-to-low or low-to-high transition within the bit period).
This means that to transmit one bit, two signaling elements (symbols) are required.
Therefore, the number of signal changes per second (baud rate) is twice the number of bits transmitted per second (bit rate).
If $R_b$ is the bit rate and $R_s$ is the baud rate, then $R_s = 2 \times R_b$.
Consequently, the bit rate is half the baud rate: $R_b = \frac{1}{2} R_s$.

UDP is a connectionless protocol that prioritizes speed over guaranteed delivery, making it suitable for quick, small transactions. DNS (Domain Name System) primarily uses UDP for its standard query/response operations because individual requests and responses are small and fast, and retransmissions are handled at the application layer if needed. In contrast, HTTP, Telnet, and SMTP require reliable, ordered data delivery, which is provided by TCP.

To find the number of non-isomorphic Abelian groups of order 4, we use the Fundamental Theorem of Finite Abelian Groups.
First, find the prime factorization of the order: $4 = 2^2$.
The number of non-isomorphic Abelian groups of order $p^k$ is equal to the number of partitions of $k$. Here, $p=2$ and $k=2$.
The partitions of 2 are:

1. $2$: This corresponds to the cyclic group $\mathbb{Z}_4$.
2. $1+1$: This corresponds to the direct product $\mathbb{Z}_2 \times \mathbb{Z}_2$.
   These two groups are non-isomorphic (e.g., $\mathbb{Z}_4$ has an element of order 4, while $\mathbb{Z}_2 \times \mathbb{Z}_2$ does not).
   Thus, there are 2 different non-isomorphic Abelian groups of order 4.

The statement "Not every graph is connected" means "There exists at least one graph that is not connected." This can be formalized as $\exists x (Graph(x) \wedge \neg Connected(x))$.

Let's evaluate each option:

1. A. $\neg \forall x (Graph(x)\Rightarrow Connected(x))$
   This is equivalent to $\exists x \neg (Graph(x)\Rightarrow Connected(x))$. Using the equivalence $\neg (A \Rightarrow B) \equiv A \wedge \neg B$, this simplifies to $\exists x (Graph(x) \wedge \neg Connected(x))$. This directly represents the statement.

2. C. $\neg \forall x(\neg Graph(x) \vee Connected(x))$
   Using the equivalence $A \Rightarrow B \equiv \neg A \vee B$, the expression $(\neg Graph(x) \vee Connected(x))$ is equivalent to $(Graph(x) \Rightarrow Connected(x))$. is identical to option A and also represents the statement.

3. D. $\forall x(Graph(x) \Rightarrow \neg Connected(x))$
   This statement translates to "For every x, if x is a graph, then x is not connected," which means "All graphs are disconnected." This is a much stronger claim than "Not every graph is connected" (which only requires at least one disconnected graph). For example, if there's one connected graph and one disconnected graph, "Not every graph is connected" is true, but D is false. Thus, D does NOT represent the statement.

4. B. $\exists x(Graph(x) \Rightarrow \neg Connected(x))$
   In problems of this type, it is a common implicit assumption that the domain of discourse is restricted to the type of objects being discussed (i.e., graphs). If the domain consists only of graphs, then $Graph(x)$ is always true. Under this assumption, $Graph(x) \Rightarrow \neg Connected(x)$ simplifies to $True \Rightarrow \neg Connected(x)$, which is $\neg Connected(x)$. So, B becomes $\exists x (\neg Connected(x))$, which means "There exists a graph that is not connected." This represents the original statement.

Given that A, B, and C represent the statement (under the common implicit assumption for B), D is the only option that does NOT represent the statement.

The final answer is $\boxed{D}$

A connected graph has an Eulerian circuit if and only if every vertex has an even degree.

1. A. Any k-regular graph where k is an even number. This is not necessarily true because the graph might not be connected (e.g., two disjoint $K_3$ graphs, each 2-regular).
2. B. A complete graph on 90 vertices ($K_{90}$). In $K_{90}$, every vertex has degree $90-1=89$. Since 89 is odd, $K_{90}$ does not have an Eulerian circuit.
3. C. The complement of a cycle on 25 vertices ($\bar{C}_{25}$).
   • A cycle graph $C_{25}$ has 25 vertices, and each vertex has degree 2.
   • The degree of a vertex $v$ in its complement $\bar{C}_{25}$ is $(25-1) - \text{deg}_{C_{25}}(v) = 24 - 2 = 22$.
   • Since 22 is an even number, all vertices in $\bar{C}_{25}$ have an even degree.
   • For $n \ge 4$, the complement of a cycle graph $\bar{C}_n$ is connected. Since $n=25$, $\bar{C}_{25}$ is connected.
   • Thus, $\bar{C}_{25}$ is connected and all its vertices have even degrees, so it has an Eulerian circuit.

Let $E = \{2, 4, 6, 8, 10, 12, 14, 16, 18, 20\}$ be the set of all even numbers from 1 to 20. There are 10 even numbers.

Consider any permutation of the numbers $1, 2, \dots, 20$. In this permutation, the 10 even numbers will appear in some order. For example, if we consider the numbers 2, 4, and 6, one possible relative order is (4, 2, 6), meaning 4 appears before 2, and 2 appears before 6.

We are interested in the event that 2 appears at an earlier position than any other even number. This means that among the 10 even numbers, 2 must be the first to appear in the permutation.

By symmetry, each of the 10 even numbers is equally likely to appear first among the even numbers.
There are $10!$ ways to arrange these 10 even numbers among themselves within the permutation.
The number of arrangements where 2 appears first is $9!$ (since 2 is fixed as the first, and the remaining 9 even numbers can be arranged in $9!$ ways).

The probability is the ratio of favorable arrangements to the total arrangements for the relative order of the even numbers:
$P(\text{2 appears first among evens}) = \frac{\text{Number of arrangements where 2 is first}}{\text{Total number of arrangements of even numbers}} = \frac{9!}{10!} = \frac{1}{10}$

Let $\lambda$ be an eigenvalue of matrix $A$, and let $v$ be a corresponding eigenvector, so $Av = \lambda v$.
Let the block matrix be

. We seek its eigenvalues.
Consider a vector

.
Then

.
Thus, $\lambda+1$ is an eigenvalue of $M$.

Now consider a vector

.
Then

.
Thus, $\lambda-1$ is an eigenvalue of $M$.

The eigenvalues of $A$ are -5, -2, 1, 4.
The possible eigenvalues for $M$ are $\lambda \pm 1$:
For $\lambda = -5$: $-5 \pm 1 \implies -4, -6$.
For $\lambda = -2$: $-2 \pm 1 \implies -1, -3$.
For $\lambda = 1$: $1 \pm 1 \implies 0, 2$.
For $\lambda = 4$: $4 \pm 1 \implies 3, 5$.

The set of all eigenvalues of $M$ is $\{-6, -4, -3, -1, 0, 2, 3, 5\}$.
Comparing with the options, 2 is an eigenvalue of $M$.

The final answer is $\boxed{C}$

The set $X$ is defined by $x_1+x_2+x_3=0$, which is a homogeneous linear equation. Thus, $X$ is a subspace of $R^3$, specifically a plane through the origin, with dimension $3-1=2$.

Consider the given vectors $v_1 = [1,-1,0]^T$ and $v_2 = [1,0,-1]^T$.
First, verify they are in $X$:
For $v_1$: $1 + (-1) + 0 = 0$.
For $v_2$: $1 + 0 + (-1) = 0$.
Both vectors belong to $X$.

Next, check for linear independence:
Since $v_1$ and $v_2$ are not scalar multiples of each other ($v_1 \neq c v_2$ for any scalar $c$), they are linearly independent.
As $X$ is a 2-dimensional subspace and we have found two linearly independent vectors within $X$, these vectors must form a basis for $X$.

If the series converges to a limit $L$, then as $n \to \infty$, we have $x_{n+1} \to L$ and $x_n \to L$.
Substituting $L$ into the given recurrence relation:
$L = \frac{L}{2} + \frac{9}{8L}$
Subtract $\frac{L}{2}$ from both sides:
$\frac{L}{2} = \frac{9}{8L}$
Multiply both sides by $8L$:
$4L^2 = 9$
$L^2 = \frac{9}{4}$
Taking the square root, $L = \pm\frac{3}{2} = \pm 1.5$.
Since $x_0 = 0.5 > 0$, all subsequent terms $x_n$ will be positive ($x_{n+1}$ is a sum of positive terms if $x_n$ is positive). Therefore, the limit $L$ must be positive.
Thus, $L = 1.5$.

Let $n_0(w)$ be the number of $0$s in $w$ and $n_1(w)$ be the number of $1$s in $w$.
The language $L$ requires $n_0(w) \equiv 0 \pmod 3$ and $n_1(w) \equiv 0 \pmod 5$.
A state in the DFA must keep track of the remainder of $n_0(w)$ modulo $3$ and the remainder of $n_1(w)$ modulo $5$.
Let a state be represented by an ordered pair $(q_0, q_1)$, where $q_0 = n_0(w) \pmod 3$ and $q_1 = n_1(w) \pmod 5$.
The possible values for $q_0$ are $\{0, 1, 2\}$.
The possible values for $q_1$ are $\{0, 1, 2, 3, 4\}$.
The total number of such distinct pairs (states) is the product of the number of possible remainders:
$\text{Number of states} = (\text{modulus for 0s}) \times (\text{modulus for 1s}) = 3 \times 5 = 15$
All these $15$ states are reachable from the initial state $(0,0)$, and each represents a distinct equivalence class of strings, making it a minimum DFA.

The initial state is $(0,0)$, and the only accepting state is $(0,0)$.

The language $L=\{0^{i}21^{i}|i\geq 0\}$ is a Context-Free Language (CFL) because it can be generated by the CFG: $S \to 0S1 | 2$. This grammar clearly matches the count of $0$s and $1$s separated by a '2'.

It is a Deterministic Context-Free Language (DCFL) because a Deterministic Pushdown Automaton (DPDA) can recognize it:

1. Push each '0' onto the stack.
2. Upon reading '2', change state.
3. For each '1', pop a '0' from the stack.
4. Accept if the stack is empty when the input ends.
   This DPDA is deterministic as there is no ambiguity in transitions for any input symbol.

Since all CFLs are recursive, and DCFLs are a subset of CFLs, $L$ is also recursive. Therefore, it is both recursive and a deterministic CFL.

A, B, and D are non-regular due to the presence of the pattern $ww^R$, which requires matching an arbitrarily long prefix $w$ with its reverse $w^R$. This demands unbounded memory, which a finite automaton (FA) cannot provide. For example:
A. ${ww^{R}|w \\in \\{0,1\\}^{+}}$: Classic non-regular language (e.g., $0^n0^n$).
B. ${ww^{R}x|x,w \\in \\{0,1\\}^{+}}$: Contains strings like $0^n0^n1$. Pumping $0^p0^p1$ yields $0^{p-k}0^p1$, which is not in the language if $k$ is odd.
D. ${xww^{R}|x,w \\in \\{0,1\\}^{+}}$: Contains strings like $10^n0^n$. Pumping $10^{2p}$ yields $10^{2p-k}$, which is not in the language if $k$ is odd.

C. ${wxw^{R}|x,w\\in \\{0,1\\}^{+}}$: A string $s$ is in this language if it can be written as $s=wxw^R$ with $w,x \in \{0,1\}^+$. This implies that the first character of $s$ must be equal to its last character ($s_1 = s_n$). Also, $|w| \ge 1, |x| \ge 1$, so $|s| = |w|+|x|+|w^R| \ge 1+1+1=3$.
Conversely, any string $s$ of length $\ge 3$ where $s_1 = s_n$ can be written as $s_1 (s_2 \dots s_{n-1}) s_1$. We can set $w=s_1$ and $x=s_2 \dots s_{n-1}$. Since $|s| \ge 3$, $x$ is non-empty. Thus, $L_C = \{s \in \{0,1\}^* \mid |s| \ge 3 \text{ and } s_1 = s_n \}$. This language is regular and can be described by the regular expression:
$0(0|1)(0|1)^*0 \cup 1(0|1)(0|1)^*1$

To determine which expressions are not equivalent to $f(w,x,y,z)=\Sigma(0,4,5,7,8,9,13,15)$, we first identify the minterms covered by each expression.

The minterms for $f$ are $\{0,4,5,7,8,9,13,15\}$.

1. Expression (P): $x'y'z' + w'xy' + wy'z + xz$

   • $x'y'z'$ covers $m_0 (0000)$ and $m_8 (1000)$.
   • $w'xy'$ covers $m_4 (0100)$ and $m_5 (0101)$.
   • $wy'z$ covers $m_9 (1001)$ and $m_{13} (1101)$.
   • $xz$ covers $m_5 (0101)$, $m_7 (0111)$, $m_{13} (1101)$, and $m_{15} (1111)$.
   • Total minterms covered by (P): $\{0, 8, 4, 5, 9, 13, 7, 15\} = \{0,4,5,7,8,9,13,15\}$.
   • Therefore, (P) is equivalent to $f$.

2. Expression (Q): $w'y'z' + wx'y' + xz$

   • $w'y'z'$ covers $m_0 (0000)$ and $m_4 (0100)$.
   • $wx'y'$ covers $m_8 (1000)$ and $m_9 (1001)$.
   • $xz$ covers $m_5 (0101)$, $m_7 (0111)$, $m_{13} (1101)$, and $m_{15} (1111)$.
   • Total minterms covered by (Q): $\{0, 4, 8, 9, 5, 7, 13, 15\} = \{0,4,5,7,8,9,13,15\}$.
   • Therefore, (Q) is equivalent to $f$.

3. Expression (R): $w'y'z' + wx'y' + xyz + xy'z$

   • $w'y'z'$ covers $m_0 (0000)$ and $m_4 (0100)$.
   • $wx'y'$ covers $m_8 (1000)$ and $m_9 (1001)$.
   • $xyz$ covers $m_7 (0111)$ and $m_{15} (1111)$.
   • $xy'z$ covers $m_5 (0101)$ and $m_{13} (1101)$.
   • Total minterms covered by (R): $\{0, 4, 8, 9, 7, 15, 5, 13\} = \{0,4,5,7,8,9,13,15\}$.
   • Therefore, (R) is equivalent to $f$.

4. Expression (S): $x'y'z' + wx'y' + w'y$

   • $x'y'z'$ covers $m_0 (0000)$ and $m_8 (1000)$.
   • $wx'y'$ covers $m_8 (1000)$ and $m_9 (1001)$.
   • $w'y$ covers $m_4 (0100)$, $m_5 (0101)$, $m_6 (0110)$, and $m_7 (0111)$.
   • Total minterms covered by (S): $\{0, 8, 9, 4, 5, 6, 7\}$.
   • Comparing with $f$'s minterms $\{0,4,5,7,8,9,13,15\}$, expression (S) includes $m_6$ (which is not in $f$) and misses $m_{13}$ and $m_{15}$.
   • Therefore, (S) is NOT equivalent to $f$.