COMPUTER SCIENCE
29
I'APER-I
Time Allowed Three hours Maximum Marks 300
The figures in the margin indicate full marks for the questions
Candidates should answer Question Nos. 1 and 5 which are compulsory and three of the remaining questions, selecting at least one from each Section
SECTION-A
1. Define-DFA and language accepted by DFA. Define NFA and language accepted by NFA. ConstructDFA or NFA to accept the following languages over the alphabet L

All strings in having an even number of


All strings in starting and ending with the same symbol


Construct a non-deterministic PDA to accept the following language over L
L {wcwk
Draw a block diagram of the functional units of a describe the functions performed by each unit. computer and 15
Give relative and DMA. merits and demerits of Polled Interrupt I/O 5x3=15

2. With respect to acceptance of language, prove the equivalence of DFA and NFA. 20

Describe the various registers that are usually provided in a CPU (you can take 8085 as a reference). 20


Describe the operations performed by an operating system (any [our). 20


3. are zero-address, one-address and two-address 6
What are the different types of ROM and RAM? 10
What. is memory mapped 4
/11 [P.T.O.
What is a thread? How does it differ from a process? 5
What are the different states of a process? Show the possible state
transitions of a process. 10
What is preemptive scheduling? 5
What is the IEEE defi?ition of software? State four software quality
attributes.
What do you mean by object-oriented design and UML in the context
of software engineering? 14

4. Slippose G is a context-free grammar and WE where IW n 1. How long.is a derivation of W in G if G is in Chomsky normal form? 5
State the pumping lemma for CFL. Using this show that the
L {anbncn I n
is not a context-free language (CFL). 10
Define universal Tilring machine. Why is it called universal? 5

What are the attributes· of a good software? 4

What is project planning? Explain why the process of project planning is an iterative one and why a plan must be continually reviewed during a software project. 4+8=12
What is risk management? 4


What are the conditions that must hold for a deadlock to oc:cur in an operating system? 10


Write the functions of address, data and control bus. What is a stack? 9+1=10
SECTION-B
5. What is virtual memory? Why is it required? 6
What is meant by cycle stealing? 4
What do you mean by concurrent process? What is mutual exclusion? Why is it essential? 15
Point out the importances of phased development proGess. What are the basic phases of software development? 25
Define fault and failure in a software system. 10
/11 2
6. Design a Turing machine to compute a where a is a non-negative integer represented in the binary form. 15
When is a decision problem said to be decidable? Give example of an undecidable problem. . 5

Differentiate between hardwired control and micro-programmed control. 8

What is a cache memory? Name one mapping scheme of cache memory and explain it with a diagram. 3+9=12


Discuss the different interprocess communication methods in operating system. 20


7. Discuss in brief the steps of an instruction cycle. 10
What is ALU? What are its functions? 5
Write a short note on Processor Interface. 5

State producer-consumer problem. 5

What is interrupt? Explain its working in the context of I/O management in OS. 15


Differentiate betWeen top-down and bottom-up design strategies in software engineering. 8


How is SRS validated? 7
What is cohesion? 5
8. Design a push-down automaton to accept the following language Lover L -IS
L {an b2n 2 In>
Define the Chomsky hierarchy. 5

Discuss the differences 'between black box and structural testing. 10

Why is prototyping used in software development? What is the cost of software engineering? 4+6=10


How are characters represented in computers? 4


For the CPU that you have studied, explain the different addressing modes used in it. 16

3 12RQ:-I00