Indian Institute of Technology Mumbai (IIT-M) 2005 M.E Information Technology GATE IT - Question Paper

State X is the starting state of the automaton. Let the language accepted by the NFA with Y as
the only accepting state be Li. Similarly, let the language accepted by the NFA with Z as the
only accepting state be L2. Which of the subsequent statements about Li and L2 is TRUE?
(A) Li = L2
(B) LicL2
(C) L2cLi
(D) None of the above
38. Let P be a non-deterministic pushdown automaton (NPDA) with exactly 1 state, q, and
exactly 1 symbol, Z, in its stack alphabet. State q is both the starting as well as the
accepting state of the PDA. The stack is initialized with 1 Z before the begin of the operation
of the PDA. Let the input alphabet of the PDA be . Let L(P) be the language accepted by the
PDA by studying a string and reaching its accepting state. Let N(P) be the language accepted
by the PDA by studying a string and emptying its stack.
Which of the subsequent statements is TRUE?
(A) L(P) is necessarily *but N(P) is not necessarily *
(B) N(P) is necessarily * but L(P) is not necessarily *
(C) Both L(P) and N(P) is necessarily E*
(D) Neither L(P) nor N(P) are necessarily *
39. Consider the regular grammar:
S - XaYa
X-Za
Z - S a B
Y — Wa
W - Sa
Where S is the starting symbol, the set of terminals is {al and the set of nonterminals
is {S,W,X,Y,Z}.
We wish to construct a deterministic finite automaton (DFA) to recognize the identical language.
What is the minimum number of states needed for the DFA?
(A) two (B) three (C) four (D)5
40. A language L satisfies the Pumping Lemma for regular languages, and also the Pumping
Lemma for situation free languages. Which of the subsequent statements about L is TRUE?
(A) L is necessarily a regular language
(B) L is necessarily a situation free language, but not necessarily a regular language
(C) L is necessarily a non-regular language
(D) None of the above
41. provided beneath is a program which when executed spawns 2 concurrent
processes:
Semaphore X:=0;
1* Process now forks into concurrent processes P1 & P2 *1
P1 : repeat forever P2 : repeat forever
V(X); P(X);
Compute; Compute;
P(X); V(X);
Consider the subsequent statements about processes P1 and P2:
I: It is possible for process P1 to starve.

Earning:   Approval pending.