student needs: AUTOMATA AND COMPILER DESIGN

Code No: V3108 / R07

III B.Tech I Semester Regular Examinations Nov2009

COMPUTER SYSTEM ORGANIZATION

(Electrical & Electronics Engineering)

Time: 3 hours Max. Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

*****

1. (a) Write the algorithm for multiplying two floating point numbers.

(b) Multiply 0.45x1049 and 0.50x1049

2. (a) Construct a common bus system with multiplexers for four registers.

(b) Discuss the type of instruction formats with examples.[7+9]

3. (a) Write the micro-operation for the following instructions

(i) BSA (ii) BUN (iii) LDA

(b) What is interrupt cycle? Draw the flow chart which shows how computer

Handles the interrupt.[6+10]

4. (a) how is an instruction mapped to a microinstruction address.

(b) Give the implementation of conditional branching with multiplexers.[8+8]

5. (a) Explain briefly about dynamic random access memory with a neat diagram.

(b) What is the difference between static memory cell and a dynamic memory cell?

Which of these can be none destructively read out?[8+8]

6. (a) in how many ways data can be transferred from I/O units to or from memory?

Explain.

(b) Explain Daisy chaining method. [10+6]

7. (a) what is meant by pipeline hazard? Explain delay due to data dependency with

An example.

(b) Compare different types of parallel computers.[10+6]

8. (a) Discuss the difference between tightly coupled and loosely coupled

Multi processors.

(b) What is the purpose of system bus controller? Explain how the system can be

Designed to distinguish between references to local memory and references to

Common shared memory?[6+10]

@@@

Set No. 1

Code No: V3108 / R07

III B.Tech I Semester Regular Examinations Nov2009

COMPUTER SYSTEM ORGANIZATION

(Electrical & Electronics Engineering)

Time: 3 hours Max.Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

*****

1. (a) Write the steps in subtraction of unsigned numbers.

(b) Illustrate the layered view of a computer system with a diagram.[7+9]

2. How are register reference instructions recognized by the program control? Illustrate

With a flow chart. Give some example for register reference instructions.[16]

3. (a) how is a 64-word stack implemented. Write the micro operations of PUSH and

POP operations.

(b) Convert ABCDE+*-/ into reverse polish notation.

4. Give the detailed design of micro programmed control unit. Explain.[16]

5. (a) Write the types of ROM? Give Applications of ROM.

(b) Illustrate fully associative mapping with a neat diagram.[8+8]

6. (a) what is meant by Software Polling?

(b) Illustrate asynchronous read with the help of Timing Diagram[7+9].

7. (a) what are the operations in a three segmented pipeline? Give an example that uses

Delayed load with the three segment pipeline.

(b) Consider the multiplication of two 40 x 40 matrices using a vector processor. How

many product terms are there in each inner product?[8+8]

8. (a) Draw the diagram of a three dimensional hypercube. List all the paths available

from node 2 to 7.

(b) How can the cache coherence problem be solved using cache write back policy?[8+8]

@@@

Set No. 2

Code No: V3108 / R07

III B.Tech I Semester Regular Examinations Nov2009

COMPUTER SYSTEM ORGANIZATION

(Electrical & Electronics Engineering)

Time: 3 hours Max. Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

*****

1. (a) Multiply the following numbers represented in two’s complement form

(i) 0011011 x 1011011

(ii) 101101 x 110011

(b) Represent – (0.625) decimal in binary floating point form

2. (a) Draw the diagram of a bus system for four registers. Use three state buffers and

a decoder instead of multiplexers.

(b) Illustrate logic micro operations with examples.[8+8]

3. (a) What are the characteristics of RISC processor? Discuss briefly.

(b) What is a subroutine? Write the differences between subroutine and program.[8+8]

4. (a) Give the format of micro instruction. Explain the use of each field in it.

(b) Explain the difference between hardwired control and micro programmed

Control[8+8]

5. (a) What are the design decisions made in the design of cache memory system?

(b) Compare and contrast the methods of mapping memory to a cache. [8+8]

6. (a) Give the configuration of the DMA interface and its connection to the CPU

Through buses? Explain how the DMA interface functions. [16]

7. (a) Show how instruction cycle in a CPU can be processed with a four segment Pipeline.

(b)Write the pipeline conflicts that cause the instruction pipeline to deviate from

its normal operation. [8+8]

8. (a) Describe the following terminology associated with multiprocessors

i) Mutual exclusion ii) critical section iii) hardware lock

iv) Semaphore

(b) Construct the diagram for an 8x8 omega switching network. Show the switch

setting required to connect input 3 to output 1. [8+8]

@@@

Set No. 3

Code No: V3108 / R07

III B.Tech I Semester Regular Examinations Nov2009

COMPUTER SYSTEM ORGANIZATION

(Electrical & Electronics Engineering)

Time: 3 hours Max. Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

*****

1. (a) Represent decimal number 8620 in

i) Self complementary code ii) weighted code iii) EBCDIC

(b)Perform the arithmetic operation (+42) + (-13) and (-42)-(-13) in binary using signed

Two’s complement representation for negative numbers.

Normalized fraction mantissa has 16-bits.[6+4+6]

2. (a) Draw the diagram of 4-bit adder sub tractor circuit. Explain Briefly.

(b) What is the difference between a direct and indirect address instruction? How many

References to memory are needed for each type of instruction to bring the operand

Into a processor register. [8+8]

3. Briefly explain the use of overlapped register widows in RISC processor with an

Example.[16]

4. (a) Explain how the mapping from an instruction address can be done by means of read

Only memory?

(b) Write briefly about symbolic micro instruction with examples. [8+8]

5. (a) How can the virtual address translation be made faster? Illustrate with a block

Diagram.

(b) Define Hit Ratio. How are the hit ratio and cache size related? Doe the hit ration

Increases with cache bits. [8+8]

6. (a) Write the steps for data transfer in program control data transfer.

(b) Describe the types of bus arbitration techniques. [8+8]

7. (a) Write Flynn’s classification of parallel computer.

(b) Write the classification of parallel computers based on mode of accessing memory. [8+8]

8. What is cache coherence? Why is it important in shared memory multi- processor?

Systems? How can the problem be resolved with a snoopy cache controller? [16]

@@@

Set No. 4

Code No: V3115/R07 Set No. 1

III B.Tech I Semester Regular Examinations, November 2009

AUTOMOBILE ENGINEERING

(Mechanical Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) What is the main reason for the development of two stroke engines? Classify

two stroke engines. [3+3]

(b) In what respects CI engine differ from SI engine. [7]

2. (a) Describe the types of carburetors based on the direction of mixture flow. [4+4]

(b) Explain the salient features of CARTER carburetor. [4+4]

3. (a) Explain the reason for cooling an IC engine. [4]

(b) What are the various characteristics of an efficient cooling system. [4]

4. (a) Mention the components of an ignition system and describe the following with

the help of neat sketches.

i. Ignition coil [5]

ii. Contact breaker [5]

(b) Sketch and explain the working Distributor and name the various parts.[3+3]

5. (a) Explain the construction and working of an automotive ac generator. Why

ac-generators are popular comparing dc-generator? [4+4+2]

(b) Explain briefly the problems that may be encountered with the operation of

an alternator. [4]

6. (a) Explain the working of cone clutch used in an automobile with a neat sketch.

[4+4]

(b) How a single plate clutch is better compared to cone clutch. [8]

7. (a) Explain the constructional details of a leaf spring with the help of a neat

sketch. [4+4]

(b) Describe the features of a transverse leaf spring. [4+4]

8. Write notes for the following:

(a) Hill-holder [4]

(b) Leading and trailing shoes. [4]

1 of 2

Code No: V3115/R07 Set No. 1

(d) Break shoe material. [4]

? ? ? ? ?

2 of 2

Code No: V3115/R07 Set No. 2

III B.Tech I Semester Regular Examinations, November 2009

AUTOMOBILE ENGINEERING

(Mechanical Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. Sketch a chassis of any four wheeler and mark various parts on it. Explain the

functions of various components of automobile. [8+8]

2. (a) What are the advantages of port fuel injection systems over carburetor?[4+4]

(b) How the fuel level in the float chamber of a carburetor is maintained at con-

stant level. [4+4]

3. Explain the various types of engine cooling systems and compare them. [8+8]

4. (a) Explain the working of Centrifugal advance mechanism with the help of neat

sketch. [5+5]

(b) Explain the function of lead-acid storage Battery. [6]

5. (a) Name the various electrical components used in an automobile & give their

functions. [4+4]

(b) Explain the working of a starter switch. [4+4]

6. (a) List out the functions to be performed by the transmission system of an au-

tomobile. [8]

(b) Explain the arrangements by which engine power is transmitted to the wheels.

[8]

7. (a) Explain the constructional details of a leaf spring with the help of a neat

sketch. [4+4]

(b) Describe the features of a transverse leaf spring. [4+4]

8. (a) Explain clearly the working of the giriling mechanical brakes. [4+4]

(b) Explain the working of wheel cylinder. [4+4]

? ? ? ? ?

1 of 1

Code No: V3115/R07 Set No. 3

III B.Tech I Semester Regular Examinations, November 2009

AUTOMOBILE ENGINEERING

(Mechanical Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) What are the objects of engine lubrication? [4]

(b) How two stroke engines are being lubricated. [6]

2. (a) How the diesel fuel pump is tested for its performance? [4+4]

(b) What is the purpose of helical groove in the diesel pump. Sketch its position

for different operating conditions of the engine. [4+4]

3. (a) Explain the working of Dole thermostat. [4+4]

(b) What are the advantages of water cooling system over air cooling system. [8]

4. (a) Explain with a neat sketch of capacitance discharge ignition system. [4+4]

(b) Discuss the effect of spark advance on pressure-crank angle diagram. [8]

5. (a) Describe the working of a fuel gauge. [4+4]

(b) Explain the working of a Horn cutout relay. [4+4]

6. (a) With the help of a neat sketch, explain the construction and operation of a

constant mesh gearbox. [4+4]

(b) What do you mean by double-declutching? Explain how and why it is done?

[4+4]

7. (a) Discuss the merits of independent front suspension system. [8]

(b) Sketch a typical front suspension of a car and name its components. [4+4]

8. (a) Explain clearly how the King-Pin inclination produces directional stability?[4]

(b) Explain why do the front wheels have to toe-out in turns? [4+4]

? ? ? ? ?

1 of 1

Code No: V3115/R07 Set No. 4

III B.Tech I Semester Regular Examinations, November 2009

AUTOMOBILE ENGINEERING

(Mechanical Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) Compare the merits of front wheel drive vehicles with rear engine wheel drive

vehicles. [8]

(b) What is frameless construction? What are its advantages? [4+4]

2. (a) Draw the layout of fuel feed system in a petrol engine and name and give the

functions of each component. [4+4]

(b) Explain the mechanism provided in a A C mechanical pump to stop the fuel

supply when the carburetor float chamber is full. [4+4]

3. (a) Sketch and explain the working of water pump. [4+4]

(b) Describe Troubles of cooling systems and their remedies. [4+4]

4. (a) Mention the components of an ignition system and describe the following with

the help of neat sketches.

i. Ignition coil [5]

ii. Contact breaker [5]

(b) Sketch and explain the working Distributor and name the various parts.[3+3]

5. (a) What is the principle of a generator? Give its constructional details [4+4]

(b) Explain the working of a cutout relay as used in the charging circuit [8]

6. (a) What are the requirements of a clutch? [6]

(b) With the help of a neat sketch, explain the construction and operation of a

sliding mesh gearbox. [5+5]

7. (a) About what gear reduction is obtained in the differential on passenger cars

and on commercial vehicles? Does it vary from one vehicle to other. [4+4]

(b) Explain the semi floating. [4]

8. (a) Explain clearly how the King-Pin inclination produces directional stability?[4]

(b) Explain why do the front wheels have to toe-out in turns? [4+4]

? ? ? ? ?

1 of 1

Code No: V3119/R07 Set No. 1

III B.Tech I Semester Regular Examinations, November 2009

COMPUTER ORGANIZATION

( Common to Electronics & Communication Engineering and Electronics &

Instrumentation Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) In order to find the mileage given by a bike we observe how many liters of oil is

filled and how many kilometers it drove. The observation is carried for a day,

a month and a year. Which of them represents the actual performance of the

bike?. Similarly, we wanted to evaluate the performance of a computer. How

are you going to do?. What are the performance measures used in general. [6]

(b) Represent 32.75 and 18.125 in single precision IEEE 754 representation. [10]

2. (a) Explain about stack organization used in processors. What do you understand

by register stack and memory stack? [10]

(b) Explain how X=(A+B)/(A-B) is evaluated in a stack based computer. [6]

3. (a) Why do we need subroutine register in a control unit?. Explain. [8]

(b) Why do we need some bits of current microinstruction to generate address of

the next microinstruction. Support with a live example. [8]

4. (a) Draw a flowchart to explain how addition and subtraction of two fixed point

numbers can be done. Also, draw a circuit using full adders for the same. [8]

(b) Explain Booth’s logorithm with its theoretical basis. [8]

5. (a) ”In paged segmentation, the reference time increases and fragmentation de-

creases”, Justify your answer.

(b) A Virtual Memory System has an address space of 8K words and a Memory

space of 4K words and page and block sizes of 1K words. Determine the

number of page faults for the following page replacement algorithms: 1) FIFO

2) LRU if the reference string is as follows: 4,2,0,1,2,6,1,4,0,1,0,2,3,5,7 [8+8]

6. (a) Explain bit oriented and character oriented protocols in serial communication

(b) What are the different issues behind serial communication? Explain. [8+8]

7. Explain the following with related to the Instruction Pipeline

(a) Pipeline conflicts

(b) Data dependency

(d) Operand forwarding

(e) Delayed load

1 of 2

Code No: V3119/R07 Set No. 1

(f) Pre-fetch target instruction

(g) Branch target buffer

(h) Delayed branch [8×2=16]

8. (a) What are the different physical forms available to establish an inter-connection

network? Give the summary of those. [6]

(b) Explain time-shared common bus Organization [5]

? ? ? ? ?

2 of 2

Code No: V3119/R07 Set No. 2

III B.Tech I Semester Regular Examinations, November 2009

COMPUTER ORGANIZATION

( Common to Electronics & Communication Engineering and Electronics &

Instrumentation Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) Explain with an example IEEE 754 single precision floating point representa-

tion . [8]

(b) Explain about time shared bus arbitration and its disadvantages. [8]

2. . Design a circuit to increment, decrement, complement and clear a 4 bit register

using RS flip-flops. Explain the control logic. [16]

3. (a) Why do we need subroutine register in a control unit?. Explain. [8]

(b) Explain nanoinstructions and nanometry. Why do we them?. [8]

4. (a) What is the use of fast multiplication circuits. Write about array multipliers.

[8]

(b) Explain booths algorithm with its theoretical basis [8]

5. (a) Explain how the Bit Cells are organized in a Memory Chip. [8]

(b) Explain the organization of a 1K x 1 Memory with a neat sketch‘ [8]

6. What are the different kinds of I/O Communication techniques? What are the

relative advantages and disadvantages? Compare and contrast all techniques. [16]

7. (a) What is pipeline? Explain. [8]

(b) Explain arithmetic pipeline. [8]

8. Write short notes on the following

(a) Time-shared common bus organization [6]

(b) Multiport memory organization [5]

? ? ? ? ?

1 of 1

Code No: V3119/R07 Set No. 3

III B.Tech I Semester Regular Examinations, November 2009

COMPUTER ORGANIZATION

( Common to Electronics & Communication Engineering and Electronics &

Instrumentation Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. Distinguish between error detection and correction codes. What do you understand

by odd parity and even parity?. What is odd function and even function?. To

calculate odd and even parity values which functions can be used? Calculate Odd

and even parity values for all hexadecimal digits 0-9 and A-F. [16]

2. A 4-bit register and four half adder units are given. Design a circuit to increment

and decrement the content of the register. Assume unsigned numbers are available

in the register. Assume the register is made of JK flip-flops. Mention clearly control

logic. [16]

3. (a) What is a pipeline register. What is the use of it?. Explain in detail. [8]

(b) Why do we need some bits of current microinstruction to generate address of

the next microinstruction. Support with a live example. [8]

4. (a) What is the use of fast multiplication circuits. Write about array multipliers.

[8]

(b) Explain booths algorithm with its theoretical basis [8]

5. (a) A two-way set associative cache memory uses blocks of 4 words. The cache can

accommodate a total of 2048 words from main memory. The main memory

size is 124K x 32

i. Formulate the information required to construct cache Memory

ii. What is the size of cache Memory. [8]

(b) The access time of cache memory is 100ns and that of main memory is 1000ns.

It is estimated that 80% of memory requests are for read and the remaining

20% for write. The hit ratio for read access only is 0.9. A write through

procedure is used.

i. What is the average access time of the system considering only read cycles?

ii. What is the average access time of the system considering both read and

write cycles? [8]

6. (a) What is Direct Memory Access? Explain the working of DMA.

(b) What are the different kinds of DMA transfers? Explain.

7. Explain the following with related to the Instruction Pipeline

1 of 2

Code No: V3119/R07 Set No. 3

(a) Pipeline conflicts

(b) Data dependency

(d) Operand forwarding

(e) Delayed load

(f) Pre-fetch target instruction

(g) Branch target buffer

(h) Delayed branch [8×2=16]

8. What is cache coherence and why is it important in shared memory multiprocessor

systems? How can the problem be solved with a snoopy cache controller? [16]

? ? ? ? ?

2 of 2

Code No: V3119/R07 Set No. 4

III B.Tech I Semester Regular Examinations, November 2009

COMPUTER ORGANIZATION

( Common to Electronics & Communication Engineering and Electronics &

Instrumentation Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) In order to find the mileage given by a bike we observe how many liters of oil is

filled and how many kilometers it drove. The observation is carried for a day,

a month and a year. Which of them represents the actual performance of the

bike?. Similarly, we wanted to evaluate the performance of a computer. How

are you going to do?. What are the performance measures used in general. [6]

(b) Represent 32.75 and 18.125 in single precision IEEE 754 representation. [10]

2. (a) Explain about stack organization used in processors. What do you understand

by register stack and memory stack? [10]

(b) Explain how X=(A+B)/(A-B) is evaluated in a stack based computer. [6]

3. (a) Support or oppose the statement ? the control unit is a firmware?. [8]

(b) Support or oppose the statement ?If we want to add a new machine language

instruction to a processors instruction set, simply write a C program and

compile and store the resultant code in control memory?. [8]

4. (a) How many bits are needed to store the result addition, subtraction, multipli-

cation and division of two n-bit unsigned numbers. Prove. [8]

(b) What is overflow and underflow. What is the reason?. If the computer is

considered as infinite system do we still have these problems?. [8]

5. (a) A computer uses RAM chips of 1024 x 1 capacity. [10]

i. How many chips are needed and how should their address lines be con-

nected to provide a memory capacity of 1024 bytes.

ii. How many chips are needed to provide a memory capacity of 16K bytes

(b) An address space is specified by 24 bits and the corresponding memory space

by 16 bits [6]

i. How many words are there in the address space

ii. How many words are there in the memory space

6. What are the different kinds of I/O Communication techniques? What are the

relative advantages and disadvantages? Compare and contrast all techniques. [16]

7. Explain three segment instruction pipeline. Show the timing diagram and show the

timing diagram with data conflict. [16]

1 of 2

Code No: V3119/R07 Set No. 4

8. What is cache coherence? Explain different solutions to the cache coherence prob-

lem. [16]

? ? ? ? ?

2 of 2

Code No: V3127/R07 Set No. 1

III B.Tech I Semester Regular Examinations, November 2009

FORMAL LANGUAGES AND AUTOMATA THEORY

(Computer Science & Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. Construct NFAs for the following languages

(a) The set of strings over alphabet {0,1,.........,9} such that the final digit has

appeared before.

(b) The set of strings over alphabet {0,1,........,9} such that the final digit has not

appeared before.

number of positions that is a multiple of 4. Note that 0 is an allowable multiple

of 4. [4+4+8]

2. (a) Design a machine to perform a parity check on the input, that is the output

string ends in 1 if total number of 1 bits in the input string is odd and 0 if the

total number of 1 bits in the input string is even.

(b) Convert following NFA with 2-transitions into equivalent NFA without 2-

transitions as shown in figure 2b. [8+8]

Figure 2b

3. Find a Regular expression corresponding to each of the following subsets over

{0,1}*.

(a) The set of all strings containing no three consecutive 0’s.

(b) The set of all strings where the 10th symbol from right end is a 1.

1’s.

(d) The set of all strings over {0,1} in which the number of occurrences of is

divisible by 3. [4×4]

1 of 2

Code No: V3127/R07 Set No. 1

4. (a) Obtain a Right Linear Grammar for the language

L = {anbm |n >= 2,m >= 3 }

(b) Obtain a Left Linear Grammar for the DFA as shown in figure 4b. [2×8]

Figure 4b

5. (a) Show that L = {aibj/j = i2} is not context free language.

(b) List the properties of CFLs.

S!AB, A!BC/a, B!CC/b, C!a. [8+5+3]

6. (a) Construct the context free grammar G which accepts the PDA A by empty

stack, where

A=({q0, q1}, {a, b}, {Z0,Z}, , q0,Z0, )

is given by

(q0, b,Z0) = {(q0,ZZ0)}, (q0,^,Z0) = {(q0, L)}

(q0, b,Z) = {(q0,ZZ)}, (q0, a,Z) = {(q1,Z)}

(q1, b,Z) = {(q1,^)}, (q1, a,Z0) = {(q0,Z0)}

(b) What is the ID of the PDA on the string ‘bbaa’. [12+4]

7. Give a Turing machine for the following:

(a) That computes ones complement of a binary number

(b) That shifts the input string, over the alphabet (0,1) by one position right by

inserting ‘#0as the first character. [8+8]

8. (a) What is decidability? Explain any two undecidable problems.

(b) Show that the following post correspondence problem has a solution and give

the solution. [8+8]

I List A List B

1 11 11

2 100 001

3 111 11

? ? ? ? ?

2 of 2

Code No: V3127/R07 Set No. 2

III B.Tech I Semester Regular Examinations, November 2009

FORMAL LANGUAGES AND AUTOMATA THEORY

(Computer Science & Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. Construct NFAs for the following languages

(a) The set of strings over alphabet {0,1,.........,9} such that the final digit has

appeared before.

(b) The set of strings over alphabet {0,1,........,9} such that the final digit has not

appeared before.

number of positions that is a multiple of 4. Note that 0 is an allowable multiple

of 4. [4+4+8]

2. For the following NFA with 2 -moves convert it in to an NFA with out 2 -moves

and show that NFA with 2-moves accepts the same language as shown in figure 2.

[16]

Figure 2

3. Is FA is possible for the following language L = {anbn |n >= 1 } if not why? Ex-

plain? [16]

4. (a) Obtain a Right Linear Grammar for the language

L = {anbm |n >= 2,m >= 3 }

(b) Obtain a Left Linear Grammar for the DFA as shown in figure 4b. [2×8]

1 of 2

Code No: V3127/R07 Set No. 2

Figure 4b

5. (a) When is a grammar is said to be in reduced form.

(b) Convert the following grammar to GNF:

G = ({A1,A2,A3}, {a, b}, P1, A1)

Where P consists of the following:

A1 ! A2A3

A2 ! A3A1/b

A3 ! A1A2/a. [8+8]

6. (a) Write short notes on Equivalence of P.D.A. with acceptance by final state and

P.D.A. with acceptance by empty stack.

(b) Find the PDA that accepts the following language via final state:

{aibjck / i, j, k 1 and i+j=k}. [8+8]

7. (a) Define the term ‘Instantaneous description’ of a TM. Define the term ‘move’

in a TM

(b) Design a Turing machine which recognizes the language consisting of all strings

of 0s whose length is a power 2 i.e., it decides the language

L = {02n |n 0 }. [16]

8. (a) Explain about Deterministic context free language and Deterministic PDA.

(b) Show that L={anbncn : n >= 1} is a CSL. [8+8]

? ? ? ? ?

2 of 2

Code No: V3127/R07 Set No. 3

III B.Tech I Semester Regular Examinations, November 2009

FORMAL LANGUAGES AND AUTOMATA THEORY

(Computer Science & Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. Out of the following languages, which are/is accepted by given FA and explain as

shown in figure 1d.

(a) (a+b)* (c+d)* (ef)*

(b) (ab)* (cd)* (ef)*

(d) ( (ab)*+ (cd)*+ (ef)* ) *. [4×4]

Figure 1d

2. Construct DFA for given (figure 2) NFA with 2-moves. [16]

Figure 2

3. Consider the two regular expressions

r=0*+1*, s=01*10*+1*0+(0*1)*

(a) Find a string corresponding to r but not to s.

(b) Find a string corresponding to s but not to r. [8+8]

1 of 2

Code No: V3127/R07 Set No. 3

4. (a) Obtain a Right Linear Grammar for the language

L = {anbm |n >= 2,m >= 3 }

(b) Obtain a Left Linear Grammar for the DFA as shown in figure 4b. [2×8]

Figure 4b

5. (a) Define CFG and write about derivation trees.

(b) Design CFG for the following language: “The set {0n1n |n 1 }, that is the

set of all strings of one or more 0’s followed by an equal number of 1’s” 6m

S ! a

S !aAS

A ! bS

Obtain the derivation tree of the word w = abaabaa. [4+6+6]

6. Show that the languages

(a) L1={0n1m/n = m and n 1}

(b) L2={0n1m / n=2m and n 1}

Are deterministic context free languages? [8+8]

7. Design a TM that can compute proper subtraction i.e, m-n if m>n and 0 if m<n.

Give examples. [16]

8. (a) Give the CSL for L={anbncn : n >= 1}

(b) Writes the properties of recursive and recursive enumerable languages.

? ? ? ? ?

2 of 2

Code No: V3127/R07 Set No. 4

III B.Tech I Semester Regular Examinations, November 2009

FORMAL LANGUAGES AND AUTOMATA THEORY

(Computer Science & Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. Out of the following languages, which are/is accepted by given FA and explain as

shown in figure 1d.

(a) (a+b)* (c+d)* (ef)*

(b) (ab)* (cd)* (ef)*

(d) ( (ab)*+ (cd)*+ (ef)* ) *. [4×4]

Figure 1d

2. Construct DFA for NFA with 2 -moves as shown in figure 2. [16]

Figure 2

1 of 2

Code No: V3127/R07 Set No. 4

3. Find a Regular expression corresponding to each of the following subsets over

{0,1}*.

(a) The set of all strings containing no three consecutive 0’s.

(b) The set of all strings where the 10th symbol from right end is a 1.

1’s.

(d) The set of all strings over {0,1} in which the number of occurrences of is

divisible by 3. [4×4]

4. (a) Construct the left most derivative for the string aaabbabbba for the following

grammar.

S ! aB|bA

A ! aS |bAA| a

B ! bS |aBB| b

(b) For the above derivatives construct a parse tree using leftmost derivation.

[2×8]

5. (a) Explain Chomsky hierarchy.

(b) Construct PDA for set of all strings of balanced parenthesis. [8+8]

6. (a) Let G be the grammar given by

S!aABB/aAA,

A!aBB/a,

B!bBB/A

Construct the PDA that accepts the language generated by this grammar G.

(b) Define Deterministic pushdown automata. Explain with an example. [8+8]

7. Design a T.M for copying of information from one place to the other place. Assume

all the necessary. Assumptions. Give Example of the working of your T.M. [16]

8. Construct LR(0) items for the grammar given, Find its equivalent DFA. Check the

parsing by taking a suitable string.

S’!S, S!AS/^, A!aA/b. [16]

? ? ? ? ?

2 of 2

Code No: V3147/R07 Set No. 1

III B.Tech I Semester Regular Examinations, November 2009

AUTOMATA AND COMPILER DESIGN

(Information Technology)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) Draw an NFA and DFA to recognize the regular expression: (a + b)*abb.

(b) Find the regular expression recognized by the DFA as shown in figure 1b.

[8+8]

Figure 1b

2. (a) What is a recursive grammar? Explain.

(b) Consider the following recursive grammar:

i. S ! Aa |b

ii. A ! Ac |Sd

What is an equivalent grammar when the left recursion is removed? [6+10]

3. Construct the LR(1) parse table for the following augmented grammar:

S0 ! S

S ! BB

B ! bB |c. [16]

4. (a) Explain Quadruples, Triples, and Indirect Triples.

(b) Construct Quadruples, Triples, and Indirect Triples of the following expres-

sion: (a + b) * (c + d) - (a + b + c). [6+10]

5. (a) Explain Chomsky hierarchy of Languages?

(b) Give detail analysis on generic function and polymorphic function? [8+8]

6. (a) Write a notes on the static storage allocation strategy with example and dis-

cuss its limitations?

(b) Discuss about the stack allocation strategy of runtime environment with an

example? [8+8]

7. Write and Explain about Global common sub expression elimination. [16]

1 of 2

Code No: V3147/R07 Set No. 1

8. Explain about Generic code generation algorithm? [16]

? ? ? ? ?

2 of 2

Code No: V3147/R07 Set No. 2

III B.Tech I Semester Regular Examinations, November 2009

AUTOMATA AND COMPILER DESIGN

(Information Technology)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) Find a Regular Expression to the language of all strings over = {0, 1}

containing exactly two 0’s.

(b) Consider the 2- NFA as shown in figure 1b.

Figure 1b

Obtain NFA without 2-moves. [6+10]

2. Compute the FIRST and FOLLOW sets of each of the non-terminals for the fol-

lowing grammar:

P ! AQRbe |mn|DEi

A ! ab |2

Q ! q1q2 |2

R ! r1r2 |2

D ! d

E ! e. [16]

3. Construct the SLR(1) parse table for the following grammar:

S0 ! S

S ! CC

C ! cC|d.

[16]

4. (a) What is a Syntax Directed Definition? Give an example.

(b) Explain the Dependency Graph with an example. [6+10]

5. (a) Write a short notes on context sensitive language with suitable example.

(b) Write about Linear Bounded Automata. [8+8]

6. Write and Explain about algorithm for construction of equivalence trees in FOR-

TRAN? [16]

7. Write explain about Organization for an Optimizing Compiler? [16]

1 of 2

Code No: V3147/R07 Set No. 2

8. Show DAG for the following statement.

Z= X-Y+X*Y*U-V/W+X+V

and find the register requirement for its evaluation. Assume that all variables are

of fixed type and all operations require a single register. [16]

? ? ? ? ?

2 of 2

Code No: V3147/R07 Set No. 3

III B.Tech I Semester Regular Examinations, November 2009

AUTOMATA AND COMPILER DESIGN

(Information Technology)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) Design a DFA that accepts the language over the alphabet, = {0, 1, 2}

where the decimal equivalent of the language is divisible by 3.

(b) Compare compiler and an interpreter with the help of suitable examples. [8+8]

2. Construct the predictive parse table for the following grammar:

S ! iEtSS0 |a

S0 ! eS |2

E ! b. [16]

3. (a) Explain how to parse an ambiguous grammar.

(b) Construct the SLR parse table for the following ambiguous grammar:

E ! E + E |E E| (E) |a. [6+10]

4. Generate the three-address code for the following ?C? program fragment:

switch( i + j). [16]

{

case 1: x = y + z;

default: c = c - 1;

case 2: u = v + w;

}

5. Explain the following:

(a) Substitutions

(b) Instances

(d) Type variables. [4×4]

6. (a) Explain the Dynamic storage allocation facilities provided by C language?

(b) What is dangling reference in storage allocation? Explain with an example.

[8+8]

7. (a) What is global data flow analysis?

(b) Write briefly about various loop optimization techniques? [8+8]

8. Explain about Generic code generation algorithm? [16]

? ? ? ? ?

1 of 1

Code No: V3147/R07 Set No. 4

III B.Tech I Semester Regular Examinations, November 2009

AUTOMATA AND COMPILER DESIGN

(Information Technology)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

? ? ? ? ?

1. (a) Explain Regular Expressions with suitable examples.

(b) Design a DFA that accepts the language over = {a, b} of all strings that

contain the sub-string either aa or bb. [6+10]

2. (a) Write a procedure to combine two NFA?s into a single NFA. The operations

to be performed are those of concatenation, union and closure.

(b) Obtain the Non-deterministic Finite Automaton (NFA) corresponds to the

Grammar,

G = ({S, X, Y}, {a, b}, P, S), where P is defined as follows:

P ! aS |bS| bX

X ! bY |b

Y ! aY |bY| a |b. [8+8]

3. Consider the grammar: S ! (S) |a

Construct the DFA for SLR(1), CLR(1), and LALR(1) parsers and find the number

of states in each of the parser. [16]

4. Construct Quadruples, Triples and Indirect Triples of the following expression:

I = - J * (K + W). [16]

5. (a) What is importance of polymorphic functions?

(b) Write translation scheme for checking polymorphic functions? [8+8]

6. (a) Explain scope of variables with a C program when program contains nested

blocks.

(b) Explain the concept of lexical scope with nested procedures with suitable

examples. [8+8]

7. (a) Define the following:

i. Basic Block

ii. Local Optimization

iii. Global Optimization.

(b) Explain about Algebraic Transformations?

8. (a) Explain the concept of calculating cost of instructions

1 of 2

Code No: V3147/R07 Set No. 4

(b) Consider below addressing codes along with associated costs

Mode Added Cost

absolute 1

indexed 1

indirect register 0

indirect indexed 1

Compute cost of following set of statements

i. mov b, R0

Add c , R0

Mov R0,a

ii. add R2, R1

Mov R1,a

iii. Mov b , a

Add c , a. [8+8]

? ? ? ? ?

2 of 2

student needs

Pages

Sunday, August 22, 2010

AUTOMATA AND COMPILER DESIGN

No comments:

Post a Comment