GATE IT 2006
Q31.
Consider the solution to the bounded buffer producer/consumer problem by using general semaphores S, F, and E. The semaphore S is the mutual exclusion semaphore initialized to 1. The semaphore F corresponds to the number of free slots in the buffer and is initialized to N. The semaphore E corresponds to the number of elements in the buffer and is initialized to 0. \begin{array}{|l|l|}\hline \textbf{Producer Process} & \textbf{Consumer Process} \\\hline \text{Produce an item;} & \text{Wait(E);} \\ \text{Wait(F);} & \text{Wait(S);} \\ \text{Wait(S);} & \text{Remove an item from the buffer;} \\\text{Append the item to the buffer;} & \text{Signal(S);} \\ \text{Signal(S);} & \text{Signal(F);} \\ \text{Signal(E);} & \text{Consume the item;} \\\hline \end{array} Which of the following interchange operations may result in a deadlock? I. Interchanging Wait (F) and Wait (S) in the Producer process II. Interchanging Signal (S) and Signal (F) in the Consumer processQ32.
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet \{Z_0, X\} where Z_0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) \rightarrow (t, XZ_0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z_0 and X (in that order) on the stack. (s, a, Z_0) \rightarrow (s, XXZ_0) (s, \epsilon, Z_0) \rightarrow (f, \epsilon) (s, a, X) \rightarrow (s, XXX) (s, b, X) \rightarrow (t, \epsilon) (t, b, X) \rightarrow (t,\epsilon) (t, c, X) \rightarrow (u, \epsilon) (u, c, X) \rightarrow (u, \epsilon) (u, \epsilon, Z_0) \rightarrow (f, \epsilon) The language accepted by the PDA isQ33.
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?Q34.
Consider the following first order logic formula in which R is a binary relation symbol. \forall x \forall y(R(x, y) \Longrightarrow R(y, x)),The formula isQ35.
Let L be a regular language. Consider the constructions on L below: I. \text{repeat} (L) = \{ww \mid w \in L\} II. \text{prefix} (L) = \{u \mid \exists v : uv \in L\} III. \text{suffix} (L) = \{v \mid \exists u: uv \in L\} IV. \text{half} (L) = \{u \mid \exists v: | v | = | u | \text{ and } uv \in L\} Which choice of L is best suited to support your answer above?Q36.
Let L be a regular language. Consider the constructions on L below: I. \text{repeat} (L) = \{ww \mid w \in L\} II. \text{prefix} (L) = \{u \mid \exists v : uv \in L\} III. \text{suffix} (L) = \{v \mid \exists u: uv \in L\} IV. \text{half} (L) = \{u \mid \exists v: | v | = | u | \text{ and } uv \in L\}Which of the constructions could lead to a non-regular language?Q38.
Consider the regular grammar below S \rightarrow bS \mid aA \mid \epsilon A \rightarrow aS \mid bA The Myhill-Nerode equivalence classes for the language generated by the grammar areQ39.
Consider the relations r1(P, Q, R) and r2(R, S, T) with primary keys P and R respectively. The relation r_{1} contains 2000 tuples and r_{2} contains 2500 tuples. The maximum size of the join r_{1} \Join r_{2} is :Q40.
Which regular expression best describes the language accepted by the non-deterministic automaton below?