1. Consider the ALU shown below.

If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C o only (+ and -denote addition and subtraction respectively)?

• A+ B, and A-B, but not A+ 1
• A+B, and A+ 1, but not A-B
• A + B, but not A - B, or A + 1

(d) A+ B, and A-B, and A+ 1

2. Consider the following circuit composed of XOR gates and non-inverting buffers.

The non-inverting buffers have delays d 1 = 2 ns and d 2 = 4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If the following waveform is applied at input A, how many transition(s) (change of logic levels) occur(s) at B during the interval from 0 to 10 ns ?

• 1
• 2
• 3
• 4

 

THE FOLLOWING INFORMATION PERTAINS TO Q. 48-49

Consider the following assembly language program for a hypothetical processor. A, B and C are 8 bit registers. The meanings of various instructions are shown as comments.

 

MOVB, #0 ; B ¬ O

MOVC, #8 ; C ¬ 8

Z: CMP C, # 0 ; compare C with 0

JZX ; jump to X if zero flag is set

SUB C, # 1 ; C ¬ C-l

RRCA, # 1 ; right rotate A through carry by one bit. Thus:

; if the initial values of A and the carry

flag are a 7...a O and

; Co respectively, their values after the execution

of this

; instruction will be C 0a 7...a 1 and a 0 respectively.

JCY ; jump to Y if carry flag is set

JMPZ ; jump to Z

Y: ADD B, # 1 ; B ¬ B+l

JMPZ ; jump to Z

X:

 

3. If the initial value of register A is A 0, the value of register B after the program execution will be

• the number of 0 bits in A 0
• the number of 1 bits in A 0
• A 0
• 8

 

4. Which of the following instructions when inserted at location X will ensure that the value of register A after program execution is the same as its initial value?

• RRCA, #
• NOP ; no operation
• LRC A, # 1 ; left rotate A through carry flag by one bit
• ADD A, # 1

 

5. Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

(a) 1 (b) 5

(c) 7 (d) 8

­

6. Let G = ({S), {a, b} R, S) be a context free grammar where the rule set R is

S ® a S b |S S l e

Which of the following statements is true?

(a) G is not ambiguous

(b) There exist x, y, Î L (G) such that xy Ï L(G)

(c) There is a deterministic pushdown automaton that accepts L(G)

(d) We can find a deterministic finite state automaton that accepts L(G)

 

7. Consider two languages L 1 and L 2 each on the alphabet å . Let f: å ® å be a

polynomial time computable bijection such that ( " x) [x Î L 1 iff f(x) Î L 2].Further,

let f -l be also polynomial time computable..

Which of the following CANNOT be true ?

(a) L 1 Î P and L 2 is finite

(b) L 1 Î NP and L 2 Î P

(c) L 1 is undecidable and L 2 is decidable

(d) L 1 is recursively enumerable and L 2 is recursive

 

8. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table

 

	0	1	B
q0	q1, 1, R	q1, 1, R	Halt
q1	q1, 1, R	q0, 1, L	q0,B,L

 

The table is interpreted as illustrated below.

The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?

(a) M does not halt on any string in (0 + 1) +

(b) M does not halt on any string in (00 + 1)*

(c) M halts on all string ending in a 0

(d) M halts on all string ending in a 1

 

 

9. Define languages L 0 and L 1 as follows:

L 0 = {<M, w,O> I M halts on w}

L 1 = {<M, w, 1> I M does not halts on w}

Here <M, w, i> is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit, Let L = L 0 È L 1. Which of the following is true?

(a) L is recursively enumerable, but is not

(b) is recursively enumerable, but L is not

(c) Both Land L are recursive

(d) Neither L nor is recursively enumerable

 

10. Consider the NFA M shown below.

Let the language accepted by M be L. Let L 1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

• L 1 = {O, 1}* - L
• L 1 = {O, 1}*
• L 1 Í L
• L 1 = L

 

11. Consider the grammar shown below

S ® i E t S S ' l a

S' ® e S | e

E ® b

In the predictive parse table. M, of this grammar, the entries M[S', eJ and M[S ’, $] respectively are

(a) {S' ® e S} and {S' ® e } (b) {S' ® e S} and {}

(c) {S' ® e } and {S' ® e } (d) {S' ® e S, S' ® e } and {S' ® e }

 

12. Consider the grammar shown below.

S ® CC

C ® cC | d

The grammar is

• LL (1)
• SLR (1) but not LL (1)
• LALR (1) but not SLR (1)
• LR (1) but not LALR (1)

 

 

13. Consider the translation scheme shown below

S ® TR

R ® + T {print ('+');} R | e

T ® num {print (num.val);}

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2’, this translation scheme will print

• 9 + 5 + 2
• 9 5 + 2 +
• 9 5 2 + +
• + + 9 5 2

 

14. Consider the syntax directed definition shown below.

S ® id : = E {gen (id.place = E.place;);}

E ®E 1 + E 2 {t = newtemp ( );

gen (t = E 1. place + E 2.place;);

E.place = t}

E ® id {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that t i's are the temporary variable names generated by newtemp.

For the statement 'X: = Y + Z', the 3-address code sequence generated by this definition is

(a) X = Y + Z

(b) t 1 = Y + Z; X t 1

(c) t 1 = Y; t 2 = t 1 + Z; X = t2

(d) t 1 = Y; t 2 = Z; t 3 = t 1 + t 2; X = t 3

 

15. A program consists of two modules executed sequentially. Let f 1(t) and f 2(t) respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by

 

• f 1 (t) + f 2(t)
• 
• 
• max {f 1(t), f 2(t)}

THE FOLLOWING INFORMATION PERTAINS TO Q. 61-62

In a permutation a 1…a n of n distinct integers, an inversion is a pair (a i, a j) such that i <j and a i >a j