Andhra University 2006 B.E Information Technology COMPUTER SCIENCE

1
2
3
4



THE subsequent info PERTAINS TO Q. 48-49

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



MOVB, #0 ; B ¬ O

MOVC, #8 ; C ¬ eight

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

JZX ; jump to X if zero flag is set

SUB C, # one ; C ¬ C-l

RRCA, # one ; right rotate A through carry by 1 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 one and a 0 respectively.

JCY ; jump to Y if carry flag is set

JMPZ ; jump to Z

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

JMPZ ; jump to Z

X:



48. 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 one bits in A 0
A 0
8



49. Which of the subsequent instructions when inserted at location X will ensure that the value of register A after program execution is the identical as its initial value?
RRCA, #
NOP ; no operation
LRC A, # one ; left rotate A through carry flag by 1 bit
ADD A, # one



50. Consider the subsequent deterministic finite state automaton M.



Let S denote the set of 7 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) one (b) five

(c) seven (d) eight

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

S ® a S b |S S l e

Which of the subsequent 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 obtain a deterministic finite state automaton that accepts L(G)



52. Consider 2 languages L one and L two every on the alphabet å . Let f: å ® å be a

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

let f -l be also polynomial time computable..

Which of the subsequent CANNOT be actual ?

Earning:   Approval pending.