CS2304-SYSTEM SOFTWARE Questions Bank 2014


Anna University, Chennai

Anna_University,_Chennai_logo

SRINIVASAN ENGINEERING COLLEGE, PERAMBALUR

CS2304-SYSTEM SOFTWARE

16 Marks

1. Describe the architecture of SIC machine.

2. Describe SIC/EX machine architecture.

3. Discuss about any one of the RISC machine architecture.

4. Discuss about any one of the RISC machine architecture.

16 Marks

1. Describe the structure of a single pass assembler.

2. Discuss the design aspects of a two pass assembler.

3. Describe the various stages of an assembly process and explain how they are organized in two pass assembler.

4. What is meant by program relocation? Explain.

5. What is conditional assembly? Explain with example.

6. Discuss the merits of multipass assembler.

16 Marks

1. Explain the design of a loader.

2. Discuss about the absolute loader.

3. What is meant by automatic library search?

4. Explain about bootstrap loader.

clip_image0075. Explain the functions of program linking in machine dependent loader.

16 Marks

1. Explain in detail about Macro processor algorithm and data structures.

2. Explain the following machine independent macro features.

a. Concatenation of macro parameters

b. Keyword macro parameters

3. Explain in detail about MASM macro processor.

4. Explain ANSI C macro processor.

5. Explain conditional macro expansion with different types of macro conditional statements.

6. i) Why should a macro processor generate unique labels and explain how unique labels are generated.

clip_image009ii) Discuss in brief about the data structures used by a macro processor.

16 Marks

1. Explain the Editor structure with a neat diagram.

2. Write short notes on

a. Interactive debugging systems

b. Text editors

3. Write short notes on

a. User Interface Criteria

b. Features that a basic text editor should posses

4. Explain debugging functions and its capabilities.

5. i) How are user interfaces useful? Explain

ii) Discuss the nature of user interface for an interactive debugger.

6. Discuss in detail about Interactive debugging systems

CS2304-SYSTEM SOFTWARE Two Mark Questions With Answers


Anna University, Chennai

Anna_University,_Chennai_logo

SRINIVASAN ENGINEERING COLLEGE, PERAMBALUR

CS2304-SYSTEM SOFTWARE

2MARKS

UNIT I-INTRODUCTION

1. Define system software.

It consists of variety of programs that supports the operation of the computer. This software makes it possible for the user to focus on the other problems to be solved with out needing to know how the machine works internally.

Eg: operating system, assembler, loader.

2. Give some applications of OS.

-to make the computer easier to use

-to manage the resources in computer

-process management

-data and memory management

-to provide security to the user.

Operating system acts as an interface between the user and the system

Eg:windows,linux,unix,dos

3. Define compiler and interpreter.

Compiler is a set of program which converts the whole high level language program to machine language program.

Interpreter is a set of programs which converts high level language program to machine language program line by line.

4. Define loader.

Loader is a set of program that loads the machine language translated by the translator into the main memory and makes it ready for execution.

5. What is the need of MAR register.

MAR (memory address register) is used to store the address of the memory from which the data is to be read or to which the data is to be written.

6. Draw SS instruction format.

clip_image0010 7 8 15 16 19 20 31 32 35 36 47

It is a 6 byte instruction used to move L+I bytes data fro the storage location 1 to the storage location2.

Storage location1 = D1+[B1] Storage location2 = D2+[B2] Eg: MOV 60,400(3),500(4)

Base relative addressing

PC relative addressing

aTarget address is calculated using the formula

Target address =

cement+ [B]

Here The target address is calculated using the formula

Target address = Displacement + [PC]

PC-program counter

B-base register

7. Give any two difference between base relative addressing and program counter relative addressing used in SIC/XE.

Displa

Displacement lies between 0 to 4095 Displacement lies between –2048 to 2047

8. Define indirect addressing.

In the case of immediate addressing the operand field gives the memory location.The word from the given address is fetched and it gives the address of the operand.

Eg:ADD R5, [600]

Here the second operand is given in indirect addressing mode.First the word in memory location 600 is fetched and which will give the address of the operand.

9. Define immediate addressing.

In this addressing mode the operand value is given directly.There is no need to refer memory.The immediate addressing is indicated by the prefix „#‟.

Eg: ADD #5

In this instruction one operand is in accumulator and the second operand is a immediate value the value 5 is directly added with the accumulator content and the result is stored in accumulator.

10. List out any two CISC and RISC.

machine. CISC –Power PC, Cray T3E

RISC – VAX,Pentium Pro architecture

11. Following is a memory configuration:

Address Value Register R

1 5 5

5 7

6 5

What is the result of the following statement?

ADD 6(immediate) to R (indirect)

clip_image002Here 6 is the immediate data and the next value is indirect data.ie the register contains the address of the operand. Here the address of the operand is 5 and its corresponding value is 7. 6

+ [R] = 6+ [5] = 6+ 7 =13

Address

Value

Register R

4

9

6

5

7

 

6

2

 
12. Following is a memory configuration:

What is the result of the following statement? SUB 4(direct) to R (direct)

Here one operand is in the address location 4(direct addressing) and the next operand is in the register(register direct).

The resultant value is 9 –6 =3.

13. What is the name of X and L register in SIC machine and also specify its use.

A-accumulator

clip_image003Used for arithmetic operation.ie in the case of arithmetic operations one operand is in the accumulator,and other operand may be a immediate value,registre operand or memory content.The operation given in the instruction is performed and the result is stored in the accumulator register.

L-linkage register

It is used to store the return address in the case of jump to subroutine (JSUB) instructions.

14. What are the instruction formats used in SIC/XE architecture? Give any one format. Format 1 (1 byte), Format 2 (2 bytes), Format 3 (3 bytes) & Format 4(4 bytes) Are the different instructions used in SIC/XE architecture.

Format 2:

8

4

4

 
 

OPCODE

R1

R2

15. Consider the instructions in SIC/ XE programming.

10

1000

LENGTH

RESW 4

20

-----

NEW

WORD 3

What is the value assign to the symbol NEW.

In the line 10 the address is 1000 and the instruction is RESW 4.It reserves 4 word (3 x 4

=12) area for the symbol LENGTH.hence 12 is added to the LOCCTR.

Thus the value of the symbol NEW is 1000+12 =100C.

16. What is the difference between the instructions LDA # 3 and LDA THREE?

In the first instruction immediate addressing is used. Here the value 3 is directly loaded into the accumulator register.

In the second instruction the memory reference is used. Here the address (address assigned for the symbol THREE) is loaded into the accumulator register.

17. Differentiate trailing numeric and leading separate numeric.

The numeric format is used to represent numeric values with one digit per byte. In the numeric format if the sign appears in the last byte it is known as the trailing numeric. If the sign appears in a separate byte preceding the first digit then it is called as leading separate numeric.

18. What are the addressing modes used in VAX architecture?

Register direct, register deferred, auto increment and decrement, program counter relative, base

relative, index register mode and indirect addressing are the various addressing modes in VAX

architecture.

19. How do you calculate the actual address in the case of register indirect with immediate index mode?

Here the target address is calculated using the formula

T.A =(register) + displacement.

20. Write the sequence of instructions to perform the operation BETA = ALPHA + 1 using

SIC instructions.

LDA

A D D S T A

….

R E S W

ALPHA

ONE BETA

….

ALPHA 1

RESW

BETA 1

RESW

ONE 1

21. Write the sequence of instructions to perform the operation BETA = ALPHA+5 using SIC/XE instructions.

LDA ALPHA ADD STA

…. ALPHA RESW BETA RESW

22. What is the use of TD instruction in SIC architecture?

The test device (TD) instruction tests whether the addressed device is ready to send or receive a byte of data.The condition code is set to indicate the result of this test. Setting of < means the device is ready to send or receive, and = means the device is not ready.


UNIT II-ASSEMBLERS

2 Marks

1. Define the basic functions of assembler.

*translating mnemonic operation codes to their machine language equivalents.

*Assigning machine addresses to symbolic labels used by the programmer.

2. What is meant by assembler directives. Give example.

These are the statements that are not translated into machine instructions,but they provide instructions to assembler itself.

example START,END,BYTE,WORD,RESW and RESB.

3 .What is forward references?

It is a reference to a label that is defined later in a program.

Consider the statement

10 1000 STL RETADR

80 1036 RETADR RESW 1

The first instruction contains a forward reference RETADR.If we attempt to translate the program line by line,we will unable to process the statement in line 10 because we do not know the address that will be assigned to RETADR .The address is assigned later(in line 80) in the program.

4.What are the three different records used in object program?

The header record,text record and the end record are the three different records used in object program.

The header record contains the program name,starting address and length of the program. Text record contains the translated instructions and data of the program.

End record marks the end of the object program and specifies the address in the program where execution is to begin.

5.What is the need of SYMTAB(symbol table) in assembler?

The symbol table includes the name and value for each symbol in the source program,together with flags to indicate error conditions.Some times it may contains details about the data area. SYMTAB is usually organized as a hash table for efficiency of insertion and retrieval.

6. What is the need of OPTAB(operation code table) in assembler?

The operation code table contain the mnemonic operation code and its machine language equivalent. Some assemblers it may also contains information about instruction format and length.OPTAB is usually organized as a hash table,with mnemonic operation code as the key.

7.What are the symbol defining statements generally used in assemblers?

* „EQU‟-it allows the programmer to define symbols and specify their values directly.The general format is symbol EQU value

* „ORG‟-it is used to indirectly assign values to symbols.When this statement is encountered the assembler resets its location counter to the specified value.

The general format is ORG

value

In the above two statements value is a constant or an expression involving constants and previously defined symbols.

8.Define relocatable program.

An object program that contains the information necessary to perform required modification in the object code depends on the starting location of the program during load time is known as relocatable program.

9.Differentiate absolute expression and relative expression.

If the result of the expression is an absolute value (constant) then it is known as absolute expression.,

Eg : BUFEND – BUFFER

If the result of the expression is relative to the beginning of the program then it is known as relative expression.label on instructions and data areas and references to the location counter values are relative terms.

Eg: BUFEND + BUFFER

10. Write the steps required to translate the source program to object program.

· Convert mnemonic operation codes to their machine language equivalents. Convert symbolic operands to their equivalent machine addresses

· Build the machine instruction in the proper format.

· Convert the data constants specified in the source program into their internal machine representation

· Write the object program and assembly listing.

11 .What is the use of the variable LOCCTR(location counter) in assembler?

This variable is used to assign addresses to the symbols.LOCCTR is initialized to the beginning address specified in the START statement.Aftre each source statement is processed the length of the assembled instruction or data area to be generated is added to LOCCTR and hence whenever we reach a label in the source program the current value of LOCCTR gives the address associated with the label.

12. Define load and go assembler.

One pass assembler that generate their object code in memory for immediate execution is known as load and go assembler.Here no object programmer is written out and hence no need for loader.

13 .What are the two different types of jump statements used in MASM

assembler.

Near jump

A near jump is a jump to a target in the same segment and it is assembled by using a current code segment CS.

Far jump

A far jump is a jump to a target in a different code segment and it is assembled by using different segment registers .

14.What are the use of base register table in AIX assembler?

A base register table is used to remember which of the general purpose registers are currently available as base registers and also the base addresses they contain.

.USING statement causes entry to the table and .DROP statement removes the corresponding table entry.

15. Differentiate the assembler directives RESW and RESB.

RESW –It reserves the indicated number of words for data area. Eg:

10 1003 THREE RESW 1

In this instruction one word area(3 bytes) is reserved for the symbol THREE. If the memory is byte addressable then the address assigned for the next symbol is 1006.

RESB –It reserves the indicated number of bytes for data area. Eg: 10 1008 INPUT RESB 1

In this instruction one byte area is reserved for the symbol INPUT .Hence the address assigned for the next symbol is 1009.

1 6.Define modification record and give its format

This record contains the information about the modification in the object code during program relocation.the general format is

Col 1 M

Col 2-7 starting location of the address field to be modified relative to the beginning of the program

Col 8-9 length of the address field to be modified in half bytes.

17.Write down the pass numbers(PASS 1/ PASS 2) of the following activities that occur in a two pass assembler:

a. Object code generation

b. Literals added to literal table c. Listing printed

d. Address location of local symbols

Answer:

a. Object code generation - PASS 2

b. Literals added to literal table – PASS 1 c. Listing printed – PASS2

d. Address location of local symbols – PASS 1

18. What is meant by machine independent assembler features?

The assembler features that does not depends upon the machine architecture are known as

machine independent assembler features. Eg: program blocks,Literals.

19. How the register to register instructions are translated in assembler?

In the case of register to register instructions the operand field contains the register name.During the translation first the object code is converted into its corresponding machine language equivalent with the help of OPTAB.Then the SYMTAB is searched for the numeric equivalent of register and that value is inserted into the operand field.

Eg: 125 1036 RDREC CLEAR X B410

B4-macine equivalent of the opcode CLEAR

10-numeric equivalent of the register X.

20. What is meant by external references?

Assembler program can be divided into many sections known as control sections and each control section can be loaded and relocated independently of the others.If the instruction in one control section need to refer instruction or data in another control section .the assembler is unable to process these references in normal way.Such references between control are called external references.

21 .Define control section.

A control section is a part of the program that maintain its identity after assembly;each control section can be loaded and relocated independently of the others.

Control sections are most often used for subroutines.The major benefit of using control sections is to increase flexibility.

22.What is the difference between the assembler directive EXTREF and EXTDEF.

EXTDEF names external symbols that are defined in a particular control section

and may be used by other sections.

EXTREF names external symbols that are referred in a particular control section and defined in another control section.

23. Give the general format of define record.

This record gives information about external symbols that are defined in a particular control

section.The format is

Col 1 D

Col 2-7 name of external symbol defined in this control section Col 8-13 relative address of the symbol with in this control section Col 14-73 name and relative address for other external symbols.

24.Give the use of assembler directive CSECT and USE

CSECT - used to divide the program into many control sections

USE – used to divide the program in to many blocks called program blocks

25.What is the use of the assembler directive START.

The assembler directive START gives the name and starting address of the program.The format is PN START 1000

Here PN –name of the program

1000-starting address of the program.


UNIT III (LOADERS AND LINKERS)

2 Marks

1 .What are the basic functions of loaders.

Loading – brings the object program into memory for execution

Relocation – modifies the object program so that it can be loaded at an address different from the location originally specified

Linking – combines two or more separate object programs and also supplies the information needed to reference them.

2.Define absolute loader

The loader, which is used only for loading, is known as absolute loader. e.g. Bootstrap loader

3.What is meant by bootstrap loader?

This is a special type of absolute loader which loads the first program to be run by the computer. (usually an operating system)

4.What are relative (relocative) loaders?

Loaders that allow for program relocation are called relocating (relocative ) loaders.

5.What is the use of modification record?

Modification record is used for program relocation.Each modification record specifies the starting address and the length of the field whose value is to be altered and also describes the modification to be performed.

6.What are the 2 different techniques used forrelocation?

Modification record method and relocation bit method.

7.Relocation bit method

clip_image007If the relocation bit corresponding to a word of object code is set to 1,the program‟s starting address is

to be added to this word when the program is relocated.

Bit value 0 indicates no modification is required.

8.Define bit mask

The relocation bits are gathered together following the length indicator in each text record and which is called as bit mask.For e.g. the bit mask FFC(1 11111111100) specifies that the first 10 words of object code are to be modified during relocation.

9.What is the need of ESTAB.

It is used to store the name and address of the each external symbol. It also indicates in which control section the symbol is defined.

10.What is the use of the variable PROGADDR.

It gives the beginning address in memory where the linked program is to be loaded.The starting address is obtained from the operating system.

11 .Write the two passes of a linking loader.

Pass 1: assigns address to all external symbols

Pass2: it performs actual loading, relocation and linking.

1 2.Define automatic library search.

In many linking loaders the subroutines called by the program being loaded are automatically fetched from the library, linked with the main program and loaded.This feature is referred to as automatic library search.

13. List the loader options INCLUDE &DELETE. The general format of INCLUDE is

INCLUDE program_name (library name).This command direct the loader to read the designated object

program from a library and treat it as the primary loader input. The general format of DELETE

command is DELETE Csect-name

It instructs the loader to delete the named control sections from the sets of programs loaded.

14.Give the functions of the linking loader.

The linking loader performs the process of linking and relocation. It includes the operation of automatic library search and the linked programs are directly loaded.

15. Give the difference between linking loader and linkage editors.into the memory.

Linkin

The re

Time g loader editor

the pro location and linking is performed each It produces a linked version of a program and

Here t h

gram is loaded whichis written in a file for later execution e loading can be accomplished in a single Two passes are required

16..Define dynamic linking.

If the subroutine is loaded and linked to the program during its first call(run time),then it is called as dynamic loading or dynamic linking.

1 7.write the advantage of dynamic linking.

a) it has the ability to load the routine only when they are needed

b) The dynamic linking avoids the loading of entire library for each execution

18. What is meant by static executable and dynamic executable?

In static executable, all external symbols are bound and ready to run. In dynamic executables some symbols are bound at run time.

19. What is shared and private data?

The data divided among processing element is called shared data. If the data is not shared among processing elements then it is called private data.

20.Write the absolute loader algm.

Begin

Read Header record

Verify program name and length Read first text record

While record type != „E‟ do

Begin

Moved object code to specified location in memory Read next object program record

End

Jump to address specified in End record


UNIT IV (MACRO PROCESSORS)

2 Marks

1 .Define macro processor.

Macro processor is system software that replaces each macroinstruction with the corresponding

group of source language statements. This is also called as expanding of macros.

2. What do macro expansion statements mean?

These statements give the name of the macroinstruction being invoked and the arguments to be used in expanding the macros. These statements are also known as macro call.

3. What are the directives used in macro definition?

MACRO - it identifies the beginning of the macro definition

MEND - it marks the end of the macro definition

4.What are the data structures used in macro processor?

DEFTAB – the macro definitions are stored in a definition table ie it contains a macro prototype and the statements that make up the macro body.

clip_image009NAMTAB – it is used to store the macro names and it contains two pointers for each macro instruction which indicate the starting and end location of macro definition in DEFTAB.it also serves as an index to DEFTAB

ARGTAB – it is used to store the arguments during the expansion of macro invocations.

5.Define conditional macro expansion.

If the macro is expanded depends upon some conditions in macro definition (depending on the arguments supplied in the macro expansion) then it is called as conditional macro expansion.

6.What is the use of macro time variable?

Macro time variable can be used to store working values during the macro expansion. Any symbol that begins with the character & and then is not a macro instruction parameter is assumed to be a macro time variable.

7.What are the statements used for conditional macro expansion?

IF-ELSE-ENDIF statement

WHILE-ENDW statement

8.What is meant by positional parameters?

If the parameters and arguments were associated with each other according to their positions in the macro prototype and the macro invocation statement, then these parameters in macro definitions are called as positional parameters.

9.Consider the macro definition

#Define DISPLAY(EXPR) Printf(“EXPR = %d\n”,EXPR) Expand the macro instruction DISPLAY (ANS)

Ans.: Printf (“EXPR = %d\n”, ANS)

10.What are known as nested macro call?

The statement in which a macro calls on another macro,is called nested macro call. In the nested macro call, the call is done by outer macro and the macro called is the inner macro.

11. How the macro is processed using two passes? Pass 1: processing of definitions

Pass 2:actual-macro expansion.

12.Give the advantage of line by line processors.

-it avoids the extra pass over the source program during assembling

-it may use some of the utility that can be used by language translators so that can be loaded once.

13.What is meant by line by line processor

This macro processor reads the source program statements, process the statements and then the output lines are passed to the language translators as they are generated, instead of being written in an expanded file.

14. Give the advantages of general-purpose macroprocessors.

*The programmer does not need to learn about a macro facility for each compiler.

*Overall saving in software development cost and a maintenance cost

15.What is meant by general-purpose macro processors?

The macro processors that are not dependent on any particular programming language,but can be used with a variety of different languages are known as general purpose macro processors. Eg.The ELENA macro processor.

16. What are the important factors considered while designing a general purpose macroprocessors?

-comments

-grouping of statements t-okens

-syntax used for macro definitions

17.What is the symbol used to generate unique labels?

$ symbol is used in macro definition to generate unique symbols.Each macro expansion the $

symbol is replaced by $XX,where XX is the alpha numeric character.

1 8.How the nested macro calls are executed?

The execution of nested macro call follows the LIFO rule.In case of nested macro calls the expansion of the latest macro call is completed first.

19.Mention the tasks involved in macro expansion.

x identify the macro calls in the program

the values of formal parameters are identified

x

maintain the values of expansion time variables declared in a macro x

expansion time control flow is organized x

determining the values of sequencing symbols

x

expansion of a model statement is performed

20. How to design the pass structure of a macro assembler?

To design the structure of macro-assembler, the functions of macro preprocessor and the

conventional assembler are merged. After merging, the functions are structured into passes of the

macro assembler.


UNIT V (TEXT EDITORS)

2 Marks

1 .Define interactive editor?

An interactive editor is a computer program that allows a user to create and revise a target document. The term document includes objects such as computer programs, text, equations, tables, diagrams, line art, and photographs any thing that one might find on a printed page.

2. What are the tasks performed in the editing process?

4 tasks

1. select the part of the target document to be viewed and manipulated.

2. Determine how to format this view on-line and how to display it.

3. Specify and execute operations that modify the target document.

4. Update the view appropriately.

3. What are the three categories of editor‟s devices?

1. Text device/ String devices

2. Button device/Choice devices

3. Locator device

4.What is the function performed in editing phase?

In the actual editing phase, the target document is created or altered with a set of operations such as insert, delete, replace, move and copy.

5.Define Locator device?

Locator devices are two-dimensional analog-to-digital converters that position a cursor symbol on the screen by observing the user‟s movement of the device. The most common such devices for editing applications are the mouse and the data tablet.

6.What is the function performed in voice input device?

Voice-input devices, which translate spoken words to their textual equivalents, may prove to be the text input devices of the future. Voice recognizers are currently available for command input on some systems.

7.What are called tokens?

The lexical analyzer tracks the source program one character at a time by making the source program into sequence of atomic units is called tokens.

8.Name some of typical tokens.

Identifiers, keywords, constants, operators and punctuation symbols such as commas and parentheses are typical tokens.

9. What is meant by lexeme?

The character that forms a token is said to be a lexeme.

1 0.Mention the main disadvantage of interpreter.

The main disadvantage of interpreter is that the execution time of interpreted program is slower than

that of a corresponding compiled object program.

11 .What is meant by code optimization?

The code optimization is designed to improve the intermediate code, which helps the object program to run faster and takes less space.

12. What is error handler?

The error handler is used to check if there is an error in the program. If any error, it should warn

the programmer by instructions to proceed from phase to phase.

13 .Name some of text editors.

-line editors

-stream editors

-screen editors

-word processors structure editors

14.What for debug monitors are used?

Debug monitors are used in obtaining information for localization of errors.

15 .Mention the features of word processors.

x moving text from one place to another

x merging of text

x Searching

x word replacement

1 6.What are the phases in performing editing process?

a. Traveling phase b. Filtering phase

c. Formatting phase d. Editing phase

17.Define traveling phase.

The phase specifies the region of interest. Traveling is achieved using operations such as next screenful, bottom, find pattern.

1 8.Filtering phase.

The selection of what is to be viewed and manipulated in given by filtering.

1 9.Editing phase

In this phase, the target document is altered with the set of operations such as insert, delete, replace, move and copy.

20.Define user interface?

User interface is one, which allows the user to communicate with the system in order to perform certain tasks. User interface is generally designed in a computer to make it easier to use.

21 .Define input device?

Input device is an electromechanical device, which accepts data from the outside world and translates them into a form, which the computer can interpret.

22.Define output devices

Output devices the user to view the elements being edited and the results of the editing operations.

23.Define editor structure.

The command language processor accepts input from the users input devices and analyzes the tokens and syntactic structure of the commands.

24.Define interactive debugging systems

An interactive debugging system provides programmers with facilities that aid in the testing and debugging of programs.

1. Debugging functions and capabilities

2. Relationship with other parts of the system

3. User interface criteria.

26. What are the basic types of computing environments used in editors functions? Editor‟s

function in three basic types of computing environments

i.Time sharing

ii.Stand-alone

iii.Distributed

27 .What are the methods in Interaction language of a text editor?

a. Typing –oriented or text command oriented method b. Function key interfaces

c. menu oriented method

CS2303 THEORY OF COMPUTATION Questions Bank 2014


16 MARK QUESTIONS

16 MARKS

1.Prove that ,if L is accepted by an NFA with є-transitions, then L is accepted by an NFA

without є-transitions.

Refer page no:26,Theorem 2.2

2.Prove that for every regular expression there exist an NFA with є-transitions.

Refer page no:30,Theorem 2.3

3.If L is accepted by an NFA with ε-transition then show that L is accepted by an NFA

without ε-transition

3.Construct the NFA with є-transitions from the given regular expression.

clip_image007If the regular expression is in the form of ab then NFA is a b

If the regular expression is in a+b form then NFA is

є a є

clip_image008є b є

If the regular expression is in a* form then NFA is

clip_image009є a є

4.conversion of NFA to DFA

Draw the NFA’s transition table

Take the initial state of NFA be the initial state of DFA. Transit the initial state for all the input symbols.

If new state appears transit it again and again to make all state as old state. All the new states are the states of the required DFA

Draw the transition table for DFA

Draw the DFA from the transition table.

5.Conversion of DFA into regular expression.

Arden’s theorem is used to find regular expression from the DFA. using this theorem if the equation is of the form R=Q+RP,we

can write this as R=QP*.

Write the equations for all the states.

Apply Ardens theorem and eliminate all the states.

Find the equation of the final state with only the input symbols. Made the simplifications if possible

The equation obtained is the required regular expression.

6.Leftmost and rightmost derivations.

If we apply a production only to the leftmost variable at every step to derive the required string then it is called as leftmost derivation.

If we apply a production only to the rightmost variable at every step to derive the required string then it is called as rightmost derivation.

Example:

Consider G whose productions are S->aAS|a , A->SbA|SS|ba.For the string w=aabbaa find the leftmost and rightmost derivation.

LMD: S=>aAS

=>aSbAS

=>aabAS

=>aabbaS

=>aabbaa

RMD: S=>aAS

=>aAa

=>aSbAa

=>aSbbaa

=>aabbaa

7. Prove that for every derivations there exist a derivation tree.

Refer page no: 84,Theorem 4.1

8.Construction of reduced grammar.

• Elimination of null productions

- In a CFG,productions of the form A->є can be eliminated, where A is a variable.

• Elimination of unit productions.

- In a CFG,productions of the form A->B can be eliminated, where A

and B are variables.

• Elimination of Useless symbols.

- these are the variables in CFG which does not derive any terminal or not reachable from the start symbols. These can also eliminated.

-

9. Chomsky normal form(CNF)

If the CFG is in CNF if it satisfies the following conditions

- All the production must contain only one terminal or only two variables in the right hand side.

Example: Consider G with the production of S->aAB , A-> bC , B->b, C->c.

G in CNF is S->EB , E->DA , D-> a , A->FC , F-> b , B->b , C-> c.

10.Conversion of CFL in GNF.

Refer page no: 97,Example 4.10

11.Design a PDA that accepts the language {wwR | w in (0+1)*}.

Refer page no:112,Example 5.2

12. Prove that if L is L(M2) for some PDA M2,then L is N(M1) for some PDA M1.

Refer page no:114,Theorem 5.1

13.If L is a context-free language, then prove that there exists a PDA M such that

L=N(M).

Refer page no: 116,Theorem 5.3

14.Conversion of PDA into CFL.

Theorem: refer page no:117

Example: refer page no :119

15.State and prove the pumping lemma for CFL Refer page no: 125,Theorem 6.1

16.Explain the various techniques for Turing machine construction.

- storage in finite control

- multiple tracks

- checking off symbols

- shifting over

- subroutines.

For explanation refer page no 153-158

17.Briefly explain the different types of Turing machines.

- two way finite tape TM

- multi tape TM

- nondeterministic TM

- multi dimensional TM

- multihead TM

For explanation refer page no 160-165

18.Design a TM to perform proper subtraction.

Refer page no: 151,Example 7.2

19Design a TM to accept the language L={0n1n | n>=1} Refer page no:149,Example 7.1

20. Explain how a TM can be used to determine the given number is prime or not?

It takes a binary input greater than 2,written on the first track, and determines whether it is a prime. The input is surrounded by the symbol $ on the first track.

To test if the input is a prime, the TM first writes the number 2 in binary on the second track and copies the first track on to the third. Then the second track is subtracted as many times as possible, from the third track effectively dividing the third track by the second and leaving the remainder.

If the remainder is zero, the number on the first track is not a prime.If the remainder is non zero,the number on the second track is increased by one.If the second track equals the first,the number on the first track is the prime.If the second is less than first,the whole operation is repeated for the new number on the second track.

21.State and explain RICE theorem.

Refer page no: 188,Theorem 8.6

22.Define Lu and prove that Lu is recursive enumerable.

Refer page no: 183,Theorem 8.4

23. Define Ld and prove that Ld is undecidable.

Refer page no: 182.

24.Prove that if a language L and its complement are both recursively enumerable, then L

is recursive.

Refer page no: 180,Theorem 8.3

25.Prove that the halting problem is undecidable.

Refer page no: 187

26. Prove that a language L is accepted by some ε-NFA if and only if L is accepted by some DFA.

27. Construct DFA equivalent to the NFA given

s | i

0

1

p

{p,q}

p

q

r

r

r

s

-

s

s

s

28. Consider the following ε-NFA.Compute the ε-closure of each state and find it’s

equivalent DFA

s | i

ε

a

b

c

p

{q}

{p}

ф

ф

q

{r}

ф

{q}

ф

r

ф

ф

ф

{r}

29. Prove that a language L is accepted by some DFA iff L is accepted by some NFA.

30. Prove that if L=N(PN) for some PDA PN=(Q, Σ,Γ,δN,q0,Z0),then there is a PDA PF

such that L=L(PF).

31. i)Obtain the chomsky normal form equivalent to the grammar.

S->AB|CA , B->BC|AB ,A->a ,C->aB|b (6)

ii)Convert the grammar S->AB,A->BS|b,B->SA|a into greibach normal form.(10)

32. Define the language Lu.Check whether Lu is recursively enumerable or recursive.

Justify your answers.

BOOK REFERED

1.Introduction to automata theory,languages,and computation

by John E.Hopcroft,Jeffery D,Ullman

CS2303 THEORY OF COMPUTATION Two Mark Questions With Answers 2014


Anna University, Chennai

Anna_University,_Chennai_logo

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

SUBJECT CODE:CS2303

THEORY OF COMPUTATION

TWO MARK QUESTIONS-ANSWERS

2 MARKS QUESTIONS WITH ANSWERS & 16 MARK QUESTIONS

UNIT I AUTOMATA

1. What is deductive proof?

A deductive proof consists of a sequence of statements, which starts from a hypothesis, or a given statement to a conclusion. Each step is satisfying some logical

principle.

2.Give the examples/applications designed as finite state system.

Text editors and lexical analyzers are designed as finite state systems. A lexical analyzer scans the symbols of a program to locate strings corresponding to identifiers,

constants etc, and it has to remember limited amount of information.

3.Define: (i) Finite Automaton(FA) (ii)Transition diagram

FA consists of a finite set of states and a set of transitions from state to state that occur on input symbols chosen from an alphabet ∑. Finite Automaton is denoted by a

5- tuple(Q,∑,δ,q0,F), where Q is the finite set of states , ∑ is a finite input alphabet, q0 in

Q is the initial state, F is the set of final states and δ is the transition mapping function

Q * Σ to Q.

Transition diagram is a directed graph in which the vertices of the graph correspond to the states of FA. If there is a transition from state q to state p on input a, then there is an arc labeled ‘ a ‘ from q to p in the transition diagram.

4. What are the applications of automata theory?

In compiler construction.

In switching theory and design of digital circuits.

To verify the correctness of a program.

Design and analysis of complex software and hardware systems.

To design finite state machines such as Moore and mealy machines.

5. Define proof by contrapositive.

It is other form of if then statement. The contra positive of the statement “if H

then C” is “if not C then not H”.

6.What are the components of Finite automaton model?

The components of FA model are Input tape, Read control and finite control. (a)The input tape is divided into number of cells. Each cell can hold one i/p symbol.

(b)The read head reads one symbol at a time and moves ahead.

( c)Finite control acts like a CPU. Depending on the current state and input symbol read from the input tape it changes state.

7.Differentiate NFA and DFA

NFA or Non Deterministic Finite Automaton is the one in which there exists many paths for a specific input from current state to next state. NFA can be used in

theory of computation because they are more flexible and easier to use than DFA.

Deterministic Finite Automaton is a FA in which there is only one path for a specific input from current state to next state. There is a unique transition on each input symbol.(Write examples with diagrams).

8.What is Є-closure of a state q0?

Є-closure(q0 ) denotes a set of all vertices p such that there is a path from q0 to p labeled Є. Example :

Є

q0 q1

clip_image001Є-closure(q0)={q0,q1}

9.What is a : (a) String (b) Regular language

A string x is accepted by a Finite Automaton M=(Q,Σ,δ.q0,F) if δ(q0,x)=p, for some p in F.FA accepts a string x if the sequence of transitions corresponding to the

symbols of x leads from the start state to accepting state.

The language accepted by M is L(M) is the set {x | δ(q0,x) is in F}. A language is regular if it is accepted by some finite automaton.

10.Define Induction principle.

• Basis step:

P(1) is true.

• Assume p(k) is true.

• P(K+1) is shown to be true.


UNIT II REGULAR EXPRESSIONS AND LANGUAGES

1.What is a regular expression?

A regular expression is a string that describes the whole set of strings according to certain syntax rules. These expressions are used by many text editors and utilities to

search bodies of text for certain patterns etc. Definition is: Let Σ be an alphabet. The regular expression over Σ and the sets they denote are:

i. Φ is a r.e and denotes empty set. ii. Є is a r.e and denotes the set {Є}

iii. For each ‘a’ in Σ , a+ is a r.e and denotes the set {a}.

iv. If ‘r’ and ‘s’ are r.e denoting the languages R and S respectively then (r+s),

(rs) and (r*) are r.e that denote the sets RUS, RS and R* respectively.

2. Differentiate L* and L+

L* denotes Kleene closure and is given by L* =U Li

i=0

example : 0* ={Є ,0,00,000,…………………………………}

Language includes empty words also.

L+ denotes Positive closure and is given by L+= U Li

i=1 example:0+={0,00,000,……………………………………..}

3.What is Arden’s Theorem?

Arden’s theorem helps in checking the equivalence of two regular expressions. Let P and Q be the two regular expressions over the input alphabet Σ. The regular

expression R is given as : R=Q+RP

Which has a unique solution as R=QP*.

4.Write a r.e to denote a language L which accepts all the strings which begin or end with either 00 or 11.

The r.e consists of two parts: L1=(00+11) (any no of 0’s and 1’s)

=(00+11)(0+1)*

L2=(any no of 0’s and 1’s)(00+11)

=(0+1)*(00+11) Hence r.e R=L1+L2

=[(00+11)(0+1)*] + [(0+1)* (00+11)]

5.Construct a r.e for the language which accepts all strings with atleast two c’s over the set Σ={c,b}

(b+c)* c (b+c)* c (b+c)*

6.Construct a r.e for the language over the set Σ={a,b} in which total number of a’s are divisible by 3

( b* a b* a b* a b*)*

7.what is: (i) (0+1)* (ii)(01)* (iii)(0+1) (iv)(0+1)+

(0+1)*= { Є , 0 , 1 , 01 , 10 ,001 ,101 ,101001,…………………}

Any combinations of 0’s and 1’s.

(01)*={Є , 01 ,0101 ,010101 ,…………………………………..}

All combinations with the pattern 01. (0+1)= 0 or 1,No other possibilities.

(0+1)+= {0,1,01,10,1000,0101,………………………………….}

8.Reg exp denoting a language over Σ ={1} having

(i)even length of string (ii)odd length of a string

(i) Even length of string R=(11)*

(ii) Odd length of the string R=1(11)*

9.Reg exp for:

(i)All strings over {0,1} with the substring ‘0101’

(ii)All strings beginning with ’11 ‘ and ending with ‘ab’

(iii)Set of all strings over {a,b}with 3 consecutive b’s.

(iv)Set of all strings that end with ‘1’and has no substring ‘00’

(i)(0+1)* 0101(0+1)* (ii)11(1+a+b)* ab

(iii)(a+b)* bbb (a+b)* (iv)(1+01)* (10+11)* 1

10. What are the applications of Regular expressions and Finite automata

Lexical analyzers and Text editors are two applications.

Lexical analyzers:The tokens of the programming language can be expressed

using regular expressions. The lexical analyzer scans the input program and separates the tokens.For eg identifier can be expressed as a regular expression as:

(letter)(letter+digit)*

If anything in the source language matches with this reg exp then it is recognized as an identifier.The letter is{A,B,C,………..Z,a,b,c….z} and digit is

{0,1,…9}.Thus reg exp identifies token in a language.

Text editors: These are programs used for processing the text. For example

UNIX text editors uses the reg exp for substituting the strings such as: S/bbb*/b/

Gives the substitute a single blank for the first string of two or more blanks in a given line. In UNIX text editors any reg exp is converted to an NFA with Є –transitions, this NFA can be then simulated directly.

11.Reg exp for the language that accepts all strings in which ‘a’ appears tripled over the set Σ ={a}

reg exp=(aaa)*

12.What are the applications of pumping lemma?

Pumping lemma is used to check if a language is regular or not. (i) Assume that the language(L) is regular.

(ii) Select a constant ‘n’.

(iii) Select a string(z) in L, such that |z|>n.

(iv) Split the word z into u,v and w such that |uv|<=n and |v|>=1.

(v) You achieve a contradiction to pumping lemma that there exists an ‘i’

Such that uviw is not in L.Then L is not a regular language.

13. What is the closure property of regular sets?

The regular sets are closed under union, concatenation and Kleene closure. r1Ur2= r1 +r2

r1.r2= r1r2 ( r )*=r*

The class of regular sets are closed under complementation, substitution, homomorphism and inverse homomorphism.

14.Reg exp for the language such that every string will have atleast one ‘a’ followed by atleast one ‘b’.

R=a+b+

15.Write the exp for the language starting with and has no consecutive b’s

clip_image002reg exp=(a+ab)*

16.What is the relationship between FA and regular expression.

Regular

Expression

Deterministic

clip_image003Finite

clip_image004NFA with Є-

NFA without

Є -moves


UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES

1. What are the applications of Context free languages?

Context free languages are used in:

Defining programming languages.

Formalizing the notion of parsing. Translation of programming languages. String processing applications.

2. What are the uses of Context free grammars?

Construction of compilers.

Simplified the definition of programming languages.

Describes the arithmetic expressions with arbitrary nesting of balanced parenthesis { (, ) }.

Describes block structure in programming languages. Model neural nets.

3.Define a context free grammar

A context free grammar (CFG) is denoted as G=(V,T,P,S) where V and T are finite set of variables and terminals respectively. V and T are disjoint. P is a finite set of

productions each is of the form A->α where A is a variable and α is a string of symbols from (V U T)*.

4.What is the language generated by CFG or G?

*

The language generated by G ( L(G) ) is {w | w is in T* and S =>w .That is a

G

string is in L(G) if:

(1) The string consists solely of terminals. (2) The string can be derived from S.

5.What is : (a) CFL (b) Sentential form

L is a context free language (CFL) if it is L(G) for some CFG G.

A string of terminals and variables α is called a sentential form if:

*

S => α ,where S is the start symbol of the grammar.

6. What is the language generated by the grammar G=(V,T,P,S) where

P={S->aSb, S->ab}?

S=> aSb=>aaSbb=>…………………………..=>anbn

Thus the language L(G)={anbn | n>=1}.The language has strings with equal number of a’s and b’s.

7. What is :(a) derivation (b)derivation/parse tree (c) subtree

(a) Let G=(V,T,P,S) be the context free grammar. If A->β is a production of P and

α and γ are any strings in (VUT)* then α A γ => αβγ.

G

(b) A tree is a parse \ derivation tree for G if:

(i) Every vertex has a label which is a symbol of VU TU{Є}.

(ii) The label of the root is S.

(iii) If a vertex is interior and has a label A, then A must be in V.

(iv) If n has a label A and vertices n1,n2,….. nk are the sons of the vertex n in order from left

with labels X1,X2,………..Xk respectively then A→ X1X2…..Xk must be in P. (v) If vertex n has label Є ,then n is a leaf and is the only son of its father.

(c ) A subtree of a derivation tree is a particular vertex of the tree together with all its descendants ,the edges connecting them and their labels.The label of the root may not be the start symbol of the grammar.

8. If S->aSb | aAb , A->bAa , A->ba .Find out the CFL

soln. S->aAb=>abab

S->aSb=>a aAb b =>a a ba b b(sub S->aAb) S->aSb =>a aSb b =>a a aAb b b=>a a a ba b bb

Thus L={anbmambn, where n,m>=1}

9. What is a ambiguous grammar?

A grammar is said to be ambiguous if it has more than one derivation trees for a sentence or in other words if it has more than one leftmost derivation or more than one

rightmost derivation.

10.Consider the grammarP={S->aS | aSbS | Є } is ambiguous by constructing: (a) two parse trees (b) two leftmost derivation (c) rightmost derivation

(a)

Consider a string aab :

clip_image006(b) (i)S=>aS (ii) S=>aSbS

=>aaSbS =>aaSbS

=>aabS =>aabS

=>aab =>aab

( c )(i)S=>aS (ii) S=>aSbS

=>aaSbS =>aSb

=>aaSb =>aaSbS

=>aab =>aaSb

=>aab

11. Find CFG with no useless symbols equivalent to : SAB | CA , BBC | AB, Aa , CaB | b.

S-> AB S->CA B->BC B->AB A->a

C->aB

C->b are the given productions.

* *

A symbol X is useful if S => αXβ => w

The variable B cannot generate terminals as B->BC and B->AB. Hence B is useless symbol and remove B from all productions.

Hence useful productions are: S->CA , A->a , C->b

12. Construct CFG without Є production from : S a | Ab | aBa , A b | Є , B b | A.

S->a

S->Ab

S->aBa

A->b

A->Є

B->b

B->A are the given set of production.

A->Є is the only empty production. Remove the empty production

S-> Ab , Put A-> Є and hence S-> b.

If B-> A and A->Є then B ->Є Hence S->aBa becomes S->aa . Thus S-> a | Ab | b | aBa | aa

A->b

B->b

Finally the productions are: S-> a | Ab | b | aBa | aa

A->b

B->b

13. What are the three ways to simplify a context free grammar?

By removing the useless symbols from the set of productions. By eliminating the empty productions.

By eliminating the unit productions.

14. What are the properties of the CFL generated by a CFG?

Each variable and each terminal of G appears in the derivation of some word in L

There are no productions of the form A->B where A and B are variables.

15. Find the grammar for the language L={a2n bc ,where n>1 }

let G=( {S,A,B}, {a,b,c} ,P , {S} ) where P: S->Abc

A->aaA | Є

16.Find the language generated by :S->0S1 | 0A | 0 |1B | 1

A->0A | 0 , B->1B | 1

The minimum string is S-> 0 | 1

S->0S1=>001

S->0S1=>011

S->0S1=>00S11=>000S111=>0000A111=>00000111

Thus L={ 0n 1 m | m not equal to n, and n,m >=1}

17.Construct the grammar for the language L={ an b an | n>=1}.

The grammar has the production P as: S->aAa

A->aAa | b

The grammar is thus : G=( {S,A} ,{a,b} ,P,S)

18. Construct a grammar for the language L which has all the strings which are all palindrome over Σ={a, b}.

G=({S}, {a,b} , P, S ) P:{ S -> aSa ,

S-> b S b, S-> a,

S->b,

S->Є } which is in palindrome.

19. Differentiate sentences Vs sentential forms

A sentence is a string of terminal symbols.

A sentential form is a string containing a mix of variables and terminal symbols or

all variables.This is an intermediate form in doing a derivation.

20. What is a formal language?

Language is a set of valid strings from some alphabet. The set may be empty,finite or infinite. L(M) is the language defined by machine M and L( G) is the language

defined by Context free grammar. The two notations for specifying formal languages are:

Grammar or regular expression(Generative approach) Automaton(Recognition approach)

21.What is Backus-Naur Form(BNF)?

Computer scientists describes the programming languages by a notation called

Backus- Naur Form. This is a context free grammar notation with minor changes in

format and some shorthand.

22. Let G= ( {S,C} ,{a,b},P,S) where P consists of S->aCa , C->aCa |b. Find L(G).

S-> aCa => aba

S->aCa=> a aCa a=>aabaa

S->aCa=> a aCa a=> a a aCa a a =>aaabaaa

Thus L(G)= { anban ,where n>=1 }

23.Find L(G) where G= ( {S} ,{0,1}, {S->0S1 ,S->Є },S )

S->Є , Є is in L(G)

S-> 0S1 =>0Є1=>01

S->0S1=>0 0S11=>0011

Thus L(G)= { 0n1n | n>=0}

24.What is a parser?

A parser for grammar G is a program that takes as input a string w and produces as output either a parse tree for w ,if w is a sentence of G or an error message indicating

that w is not a sentence of G.

25.Define Pushdown Automata.

A pushdown Automata M is a system (Q, Σ, Ґ ,δ ,q0, Z0,F) where

Q is a finite set of states.

Σ is an alphabet called the input alphabet.

Ґ is an alphabet called stack alphabet. q0 in Q is called initial state.

Zo in Ґ is start symbol in stack. F is the set of final states.

δ is a mapping from Q X (Σ U {Є} ) X Ґ to finite subsets of Q X Ґ *.

26.Compare NFA and PDA.

NFA

PDA

1.The language accepted by NFA is the

regular language.

The language accepted by PDA is

Context free language.

2.NFA has no memory.

PDA is essentially an NFA with

a stack(memory).

3. It can store only limited amount of

information.

It stores unbounded limit

of information.

4.A language/string is accepted only

by reaching the final state.

It accepts a language either by empty

Stack or by reaching a final state.

27.Specify the two types of moves in PDA.

The move dependent on the input symbol(a) scanned is:

δ(q,a,Z) = { ( p1, γ1 ), ( p2,γ2 ),……..( pm,γm ) }

where q qnd p are states , a is in Σ ,Z is a stack symbol and γi is in Ґ*. PDA is in state q , with input symbol a and Z the top symbol on state enter state pi Replace symbol Z by string γi.

The move independent on input symbol is (Є-move):

δ(q,Є,Z)= { ( p1,γ1 ), ( p2,γ2 ),…………( pm,γm ) }.

Is that PDA is in state q , independent of input symbol being scanned and with

Z the top symbol on the stack enter a state pi and replace Z by γi.

28.What are the different types of language acceptances by a PDA and define them.

For a PDA M=(Q, Σ ,Ґ ,δ ,q0 ,Z0 ,F ) we define : Language accepted by final state L(M) as:

*

{ w | (q0 , w , Z0 ) |--- ( p, Є , γ ) for some p in F and γ in Ґ * }.

Language accepted by empty / null stack N(M) is:

*

{ w | (q0,w ,Z0) |----( p, Є, Є ) for some p in Q}.

29.Is it true that the language accepted by a PDA by empty stack and final states are different languages.

No, because the languages accepted by PDA ‘s by final state are exactly the languages accepted by PDA’s by empty stack.

30. Define Deterministic PDA.

A PDA M =( Q, Σ ,Ґ ,δ ,q0 ,Z0 ,F ) is deterministic if:

For each q in Q and Z in Ґ , whenever δ(q,Є,Z) is nonempty ,then

δ(q,a,Z) is empty for all a in Σ.

For no q in Q , Z in Ґ , and a in Σ U { Є} does δ(q,a,Z) contains more than one element.

(Eg): The PDA accepting {wcwR | w in ( 0+1 ) * }.

31.Define Instantaneous description(ID) in PDA.

ID describe the configuration of a PDA at a given instant.ID is a triple such as (q, w ,γ ) , where q is a state , w is a string of input symbols and γ is a string of stack

symbols. If M =( Q, Σ ,Ґ ,δ ,q0 ,Z0 ,F ) is a PDA we say that

(q,aw,Zα) |-----( p, w, βα) if δ(q,a,Z) contains (p, β ).

M

‘a’ may be Є or an input symbol.

Example: (q1, BG) is in δ(q1, 0 , G) tells that (q1, 011, GGR )|---- ( q1, 11,BGGR).

32.What is the significance of PDA?

Finite Automata is used to model regular expression and cannot be used to represent non regular languages. Thus to model a context free language, a Pushdown

Automata is used.

33.When is a string accepted by a PDA?

The input string is accepted by the PDA if: The final state is reached .

The stack is empty.

34. Give examples of languages handled by PDA.

(1) L={ anbn | n>=0 },here n is unbounded , hence counting cannot be done by finite memory. So we require a PDA ,a machine that can count without limit.

(2) L= { wwR | w Є {a,b}* } , to handle this language we need unlimited counting capability .

35.Is NPDA (Nondeterministic PDA) and DPDA (Deterministic PDA)equivalent?

The languages accepted by NPDA and DPDA are not equivalent. For example: wwR is accepted by NPDA and not by any DPDA.

36. State the equivalence of acceptance by final state and empty stack.

If L = L(M2) for some PDA M2 , then L = N(M1) for some PDA M1. If L = N(M1) for some PDA M1 ,then L = L(M2) for some PDA M2.

where L(M) = language accepted by PDA by reaching a final state.

N(M) = language accepted by PDA by empty stack.


UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES

1. State the equivalence of PDA and CFL.

If L is a context free language, then there exists a PDA M such that

L=N(M).

If L is N(M) for some PDA m, then L is a context free language.

2. What are the closure properties of CFL?

CFL are closed under union, concatenation and Kleene closure. CFL are closed under substitution , homomorphism.

CFL are not closed under intersection , complementation.

Closure properties of CFL’s are used to prove that certain languages are not context free.

3. State the pumping lemma for CFLs.

Let L be any CFL. Then there is a constant n, depending only on L, such that if z is in L and |z| >=n, then z=uvwxy such that :

(i) |vx| >=1

(ii) |vwx| <=n and

(iii) for all i>=0 uviwxiy is in L.

4. What is the main application of pumping lemma in CFLs?

The pumping lemma can be used to prove a variety of languages are not context

free . Some examples are:

L1 ={ aibici | i>=1} is not a CFL.

L2= { aibjcidj | i>=1 and J>=1 } is not a CFL.

5. Give an example of Deterministic CFL.

The language L={anbn : n>=0} is a deterministic CFL

6. What are the properties of CFL?

Let G=(V,T,P,S) be a CFG

The fanout of G , Φ(G) is largest number of symbols on the RHS of

any rule in R.

The height of the parse tree is the length of the longest path from the root to some leaf.

7. Compare NPDA and DPDA.

NPDA

DPDA

1. NPDA is the standard PDA

used in automata theory.

1. The standard PDA in

practical situation is DPDA.

2. Every PDA is NPDA unless otherwise specified.

2. The PDA is deterministic in the sense ,that at most one

move is possible from any ID.

8. What are the components of PDA ?

The PDA usually consists of four components: A control unit.

A Read Unit. An input tape.

A Memory unit.

9. What is the informal definition of PDA?

A PDA is a computational machine to recognize a Context free language. Computational power of PDA is between Finite automaton and Turing machines. The

PDA has a finite control , and the memory is organized as a stack.

10. Give an example of NonDeterministic CFL

The language L={ wwR : w Є {a,b} + } is a nondeterministic CFL.

11.What is a turing machine?

Turing machine is a simple mathematical model of a computer. TM has unlimited and unrestricted memory and is a much more accurate model of a general purpose

computer. The turing machine is a FA with a R/W Head. It has an infinite tape divided into cells ,each cell holding one symbol.

12.What are the special features of TM?

In one move ,TM depending upon the symbol scanned by the tape head and state of the finite control:

Changes state.

Prints a symbol on the tape cell scanned, replacing what was written there. Moves the R/w head left or right one cell.

13. Define Turing machine.

A Turing machine is denoted as M=(Q, Σ, Ґ ,δ ,q0, B,F) Q is a finite set of states.

Σ is set of i/p symbols ,not including B.

Ґ is the finite set of tape symbols. q0 in Q is called start state.

B in Ґ is blank symbol.

F is the set of final states.

δ is a mapping from Q X Ґ to Q X Ґ X {L,R}.

14.Define Instantaneous description of TM.

The ID of a TM M is denoted as α1q α2 . Here q is the current state of M is in Q;

α1 α2 is the string in Ґ * that is the contents of the tape up to the rightmost nonblank symbol or the symbol to the left of the head, whichever is the rightmost.

15. What are the applications of TM?

TM can be used as:

Recognizers of languages.

Computers of functions on non negative integers. Generating devices.

16.What is the basic difference between 2-way FA and TM?

Turing machine can change symbols on its tape , whereas the FA cannot change symbols on tape. Also TM has a tape head that moves both left and right side ,whereas

the FA doesn’t have such a tape head.

17.Define a move in TM.

Let X1 X2…X i-1 q Xi…Xn be an ID.

The left move is: if δ (q, Xi )= (p, Y,L) ,if i>1 then

X1 X2…X i-1 q Xi…Xn |---- X1X2… X i-2 p X i-1 Y X i+1…Xn.

M

The right move is if δ (q, Xi )= (p, Y,R) ,if i>1 then

X1 X2…X i-1 q Xi…Xn |---- X1X2… X i-1Y p X i+1…Xn.

M

18. What is the language accepted by TM?

The language accepted by M is L(M) , is the set of words in Σ * that cause M to enter a final state when placed ,justified at the left on the tape of M, with M at qo and

the tape head of M at the leftmost cell. The language accepted by M is:

{ w | w in Σ * and q0w |--- α1 p α2 for some p in F and α1 ,α2 in Ґ * }.

19. What are the various representation of TM?

We can describe TM using: Instantaneous description.

Transition table. Transition diagram.

20. What are the possibilities of a TM when processing an input string?

TM can accept the string by entering accepting state. It can reject the string by entering non-accepting state.

It can enter an infinite loop so that it never halts.

21. What are the techniques for Turing machine construction?

• Storage in finite control.

• Multiple tracks.

• Checking off symbols.

• Shifting over

• Subroutines.

22. What is the storage in FC?

The finite control(FC) stores a limited amount of information. The state of the

Finite control represents the state and the second element represent a symbol scanned.

23. What is a multihead TM?

A k-head TM has some k heads. The heads are numbered 1 through k, and move of the TM depends on the state and on the symbol scanned by each head. In one

move, the heads may each move independently left or right or remain stationary.

24.What is a 2-way infinite tape TM?

In 2-way infinite tape TM, the tape is infinite in both directions. The leftmost square is not distinguished. Any computation that can be done by 2-way infinite tape

can also be done by standard TM.

25.Differentiate PDA and TM.

PDA

TM

1. PDA uses a stack for

storage.

1. TM uses a tape that is infinite .

2.The language accepted by

PDA is CFL.

2. Tm recognizes recursively

enumerable languages.

26. What is a multi-tape Turing machine?

A multi-tape Turing machine consists of a finite control with k-tape heads and k- tapes ; each tape is infinite in both directions. On a single move depending on the state of

finite control and symbol scanned by each of tape heads ,the machine can change state print a new symbol on each cells scanned by tape head, move each of its tape head independently one cell to the left or right or remain stationary.

27.What is a multidimensional TM?

The device has a finite control , but the tape consists of a k-dimensional array of cells infinite in all 2k directions, for some fixed k. Depending on the state and

symbol scanned , the device changes state , prints a new symbol and moves its tape- head in one of the 2k directions, either positively or negatively ,along one of the k-axes.


UNIT V Undecidability

1.When we say a problem is decidable? Give an example of undecidable problem?

A problem whose language is recursive is said to be decidable. Otherwise the problem is said to be undecidable. Decidable problems have an

algorithm that takes as input an instance of the problem and determines whether the answer to that instance is “yes” or “no”.

(eg) of undecidable problems are (1)Halting problem of the TM.

2.Give examples of decidable problems.

1. Given a DFSM M and string w, does M accept w?

2. Given a DFSM M is L(M) = Φ ?

3. Given two DFSMs M1 and M2 is L(M1)= L(M2) ?

4. Given a regular expression α and a string w ,does α generate w?

5. Given a NFSM M and string w ,does M accept w?

3. Give examples of recursive languages?

i. The language L defined as L= { “M” ,”w” : M is a DFSM that accepts w} is recursive.

ii. L defined as { “M1” U “M2” : DFSMs M1 and M2 and L(M1)

=L(M2) } is recursive.

4. Differentiate recursive and recursively enumerable languages.

Recursive languages

Recursively enumerable languages

1. A language is said to be

recursive if and only if there exists

a membership algorithm for it.

1. A language is said to be r.e if

there exists a TM that accepts it.

2. A language L is recursive iff

there is a TM that decides L. (Turing decidable languages). TMs

that decide languages are algorithms.

2. L is recursively enumerable iff

there is a TM that semi-decides L. (Turing acceptable languages). TMs

that semi-decides languages are not algorithms.

5. What are UTMs or Universal Turing machines?

Universal TMs are TMs that can be programmed to solve any problem, that can be solved by any Turing machine. A specific Universal Turing machine U is:

Input to U: The encoding “M “ of a Tm M and encoding “w” of a string w. Behavior : U halts on input “M” “w” if and only if M halts on input w.

6. What is the crucial assumptions for encoding a TM?

There are no transitions from any of the halt states of any given TM . Apart from the halt state , a given TM is total.

7. What properties of recursive enumerable seta are not decidable?

Emptiness

Finiteness

Regularity

Context-freedom.

8.Define L.When is a trivial property?

Lℓ is defined as the set { <M> | L(M) is in ℓ. }

ℓ is a trivial property if ℓ is empty or it consists of all r.e languages.

9. What is a universal language Lu?

The universal language consists of a set of binary strings in the form of

pairs (M,w) where M is TM encoded in binary and w is the binary input string.

Lu = { < M,w> | M accepts w }.

10.What is a Diagonalization language Ld?

The diagonalization language consists of all strings w such that the TM M

whose code is w doesnot accept when w is given as input.

11. What properties of r.e sets are recursively enumerable?

L ≠ Φ

L contains at least 10 members.

w is in L for some fixed w. L ∩ Lu ≠ Φ

12. What properties of r.e sets are not r.e?

L = Φ

L = Σ *.

L is recursive

L is not recursive. L is singleton.

L is a regular set. L - Lu ≠ Φ

13.What are the conditions for Lto be r.e?

Lℓ is recursively enumerable iff ℓ satisfies the following properties:

ii.

If L is an infinite language in ℓ ,then there is a finite subset

of L in ℓ.

iii.

The set of finite languages in ℓ is enumaerable.

 
i. If L is in ℓ and L is a subset of L ,then L is in ℓ (containment property)

14. What is canonical ordering?

Let Σ* be an input set. The canonical order for Σ * as follows . List words in order of size, with words of the same size in numerical order. That is let Σ ={

x0,x1,…x t-1 } and xi is the digit i in base t.

(e.g) If Σ ={ a,b } the canonical order is Є , a ,b , aa, ab ,……..

15. How can a TM acts as a generating device?

In a multi-tape TM ,one tape acts as an output tape, on which a symbol, once written can never be changed and whose tape head never moves left. On that output

tape , M writes strings over some alphabet Σ , separated by a marker symbol # , G(M) ( where G(M) is the set w in Σ * such that w is finally printed between a pair of #’s on the output device ).

16. What are the different types of grammars/languages?

• Unrestricted or Phase structure grammar.(Type 0 grammar).(for TMs)

• Context sensitive grammar or context dependent grammar (Type1)(for

Linear Bounded Automata )

• Context free grammar (Type 2) (for PDA)

• Regular grammar (Type 3) ( for Finite Automata). This hierarchy is called as Chomsky Hierarchy.

17. What is a PS or Unrestricted grammar?

A grammar without restrictions is a PS grammar. Defined as G=(V,T,P,S) With P as :

Φ A ψ -> Φ α ψ where A is variable and Φ α ψ is replacement string. The languages generated by unrestricted grammars are precisely those accepted by Turing machines.

18. State a single tape TM started on blank tape scans any cell four or more times is decidable?

If the TM never scans any cell four or more times , then every crossing sequence is of length at most three. There is a finite number of distinct crossing

sequence of length 3 or less. Thus either TM stays within a fixed bounded number of tape cells or some crossing sequence repeats.

19.Does the problem of “ Given a TM M ,does M make more than 50 moves on input B “?

Given a TM M means given enough information to trace the processing of a fixed string for a certain fixed number of moves. So the given problem is

decidable.

20. Show that AMBIGUITY problem is un-decidable.

Consider the ambiguity problem for CFGs. Use the “yes-no” version of AMB.

An algorithm for FIND is used to solve AMB. FIND requires producing a word with

two or more parses if one exists and answers “no” otherwise. By the reduction of

AMB to FIND we conclude there is no algorithm for FIND and hence no algorithm for AMB.

21.State the halting problem of TMs.

The halting problem for TMs is:

Given any TM M and an input string w, does M halt on w?

This problem is undecidable as there is no algorithm to solve this problem.

22.Define PCP or Post Correspondence Problem.

An instance of PCP consists of two lists , A = w1,w2,….wk

and B = x1,…..xk of strings over some alphabet Σ .This instance of PCP has a

solution if there is any sequence of integers i1,i2,..im with m >=1 such that

wi1, wi2,…wim = xi1,xi2 ,…xim

The sequence i1 ,i2 ,…im is a solution to this instance of PCP.

23.Define MPCP or Modified PCP.

The MPCP is : Given lists A and B of K strings from Σ * ,say

A = w1 ,w2, …wk and B= x1, x2,…..xk

does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..wir = x1xi1xi2…xir?

24 . What is the difference between PCP and MPCP?

The difference between MPCP and PCP is that in the MPCP ,a solution is required to start with the first string on each list.

25. What are the concepts used in UTMs?

Stored program computers.

Interpretive Implementation of Programming languages.

Computability.

26.What are(a) recursively enumerable languages (b) recursive sets?

The languages that is accepted by TM is said to be recursively enumerable (r. e )

languages. Enumerable means that the strings in the language can be enumerated by

the TM. The class of r. e languages include CFL’s.

The recursive sets include languages accepted by at least one TM that halts on all inputs.

27. When a recursively enumerable language is said to be recursive ? Is it true that the language accepted by a non-deterministic Turing machine is different from recursively enumerable language?

A language L is recursively enumerable if there is a TM that accepts L and recursive if there is a TM that recognizes L. Thus r.e language is Turing acceptable and

recursive language is Turing decidable languages.

No , the language accepted by non-deterministic Turing machine is same as recursively enumerable language.

CS2302 -COMPUTER NETWORKS Two Mark Questions With Answers 2014


Anna University, Chennai

Anna_University,_Chennai_logo

CS2302 -COMPUTER NETWORKS

TWO MARKS WITH SIXTEEN MARKS QUESTIONS UNIT- I

1. What are the three criteria necessary for an effective and efficient network?

The most important criteria are performance, reliability and security.

Performance of the network depends on number of users, type of transmission medium, and the capabilities of the connected h/w and the efficiency of the s/w.

Reliability is measured by frequency of failure, the time it takes a link to recover from the failure and the network’s robustness in a catastrophe.

Security issues include protecting data from unauthorized access and viruses.

2. Group the OSI layers byfunction?

The seven layers of the OSI model belonging to three subgroups.

Physical, data link and network layers are the network support layers; they deal with the physical aspects of moving data from one device to another.

Session, presentation and application layers are the user support layers; they allow interoperability among unrelated software systems.

The transport layer ensures end-to-end reliable data transmission.

3. What are header and trailers and how do they get added and removed?

Each layer in the sending machine adds its own information to the message it receives from the layer just above it and passes the whole package to the layer just below it. This information is added in the form of headers or trailers. Headers are added to the message at the layers 6,5,4,3, and 2. A trailer is added at layer2. At the receiving machine, the headers or trailers attached to the data unit at the corresponding sending layers are removed, and actions appropriate to that layer are taken.

4. What are the features provided by layering?

Two nice features:

• It decomposes the problem of building a network into more manageable

Components.

• It provides a more modular design.

5. Why are protocols needed?

In networks, communication occurs between the entities in different systems. Two

entities cannot just send bit streams to each other and expect to be understood.

For communication, the entities must agree on a protocol. A protocol is a set of rules that govern data communication.

6. What are the two interfaces provided by protocols?

• Service interface

• Peer interface

Service interface- defines the operations that local objects can perform on the protocol.

Peer interface- defines the form and meaning of messages exchanged between protocol peers to

implement the communication service.

7. Mention the different physical media?

• Twisted pair(the wire that your phone connects to)

• Coaxial cable(the wire that your TV connects to)

• Optical fiber(the medium most commonly used for high-bandwidth,

long-distance links)

• Space(the stuff that radio waves, microwaves and infra red beams

propagate through)

8. Define Signals?

Signals are actually electromagnetic waves traveling at the speed of light. The speed of

light is, however, medium dependent-electromagnetic waves traveling through copper and fiber do so at about two-thirds the speed of light in vacuum.

9. What is wave’s wavelength?

The distance between a pair of adjacent maxima or minima of a wave, typically measured in meters, is called wave’s wavelength.

10. Define Modulation?

Modulation -varying the frequency, amplitude or phase of the signal to effect the transmission of information. A simple example of modulation is to vary the power (amplitude) of a single wavelength.

11. Explain the two types of duplex?

Full duplex-two bit streams can be simultaneously transmitted over the

links at the same time, one going in each direction.

Half duplex-it supports data flowing in only one direction at a time.

12. What is CODEC?

A device that encodes analog voice into a digital ISDN link is called a CODEC, for

coder/decoder.

13. What is spread spectrum and explain the two types of spread spectrum?

Spread spectrum is to spread the signal over a wider frequency band than normal in such a way as to minimize the impact of interference from other devices.

• Frequency Hopping

• Direct sequence

14. What are the different encoding techniques?

• NRZ

• NRZI

• Manchester

• 4B/5B

15. How does NRZ-L differ from NRZ-I?

In the NRZ-L sequence, positive and negative voltages have specific meanings:

positive for 0 and negative for 1. in the NRZ-I sequence, the voltages are meaningless.

Instead, the receiver looks for changes from one level to another as its basis for recognition of

1s.

16. What are the responsibilities of data link layer?

Specific responsibilities of data link layer include the following. a) Framing b) Physical addressing c) Flow control d) Error control e) Access control.

17. What are the ways to address the framing problem?

• Byte-Oriented Protocols(PPP)

• Bit-Oriented Protocols(HDLC)

• Clock-Based Framing(SONET)

18. Distinguish between peer-to-peer relationship and a primary-secondary relationship. peer -to- peer relationship?

All the devices share the link equally.

Primary-secondary relationship: One device controls traffic and the others must transmit

through it.

19. Mention the types of errors and define the terms?

There are 2 types of errors

• Single-bit error.

• Burst-bit error.

Single bit error: The term single bit error means that only one bit of a given data unit (such as byte character/data unit or packet) is changed from 1 to 0 or from 0 to 1.

Burst error: Means that 2 or more bits in the data unit have changed from 1 to 0 from 0 to 1.

20. List out the available detection methods.

There are 4 types of redundancy checks are used in data communication.

• Vertical redundancy checks (VRC).

• Longitudinal redundancy checks (LRC).

• Cyclic redundancy checks (CRC).

• Checksum.

21. Write short notes on VRC.

The most common and least expensive mechanism for error detection is the vertical redundancy check (VRC) often called a parity check. In this technique a redundant bit called a parity bit, is appended to every data unit so, that the total number of 0’s in the unit (including the parity bit) becomes even.

22. Write short notes on LRC.

In longitudinal redundancy check (LRC), a block of bits is divided into rows and a redundant row of bits is added to the whole block.

23. Write short notes on CRC.

The third and most powerful of the redundancy checking techniques is the cyclic redundancy checks (CRC) CRC is based on binary division. Here a sequence of redundant bits, called the CRC remainder is appended to the end of data unit.

24. Write short notes on CRC checker.

A CRC checker functions exactly like a generator. After receiving the data appended with the CRC it does the same modulo-2 division. If the remainder is all 0’s the CRC is dropped and the data accepted. Otherwise, the received stream of bits is discarded and the dates are resent.

25. Define checksum.

The error detection method used by the higher layer protocol is called checksum. Checksum is based on the concept of redundancy.

26. What are the steps followed in checksum generator?

The sender follows these steps a) the units are divided into k sections each of n bits. b) All sections are added together using 2’s complement to get the sum. c) The sum is complemented and become the checksum. d) The checksum is sent with the data.

27. Mention the types of error correcting methods.

There are 2 error-correcting methods.

• Single bit error correction

• Burst error correction.

28. Write short notes on error correction?

It is the mechanism to correct the errors and it can be handled in 2 ways.

• When an error is discovered, the receiver can have the sender retransmit

the entire data unit.

• A receiver can use an error correcting coder, which automatically

corrects certain errors.

29. What is the purpose of hamming code?

A hamming code can be designed to correct burst errors of certain lengths. So the simple strategy used by the hamming code to correct single bit errors must be redesigned to be applicable for multiple bit correction.

30. What is redundancy?

It is the error detecting mechanism, which means a shorter group of bits or extra bits

may be appended at the destination of each unit.


UNIT – II

1. What are the functions of MAC?

MAC sub layer resolves the contention for the shared media. It contains

synchronization, flag, flow and error control specifications necessary to move information from one place to another, as well as the physical address of the next station to receive and route a packet.

2. What are the functions of LLC?

The IEEE project 802 models take the structure of an HDLC frame and divides it into 2

sets of functions. One set contains the end user portion of the HDLC frame – the logical address, control information, and data. These functions are handled by the IEEE 802.2 logical link control (LLC) protocol.

3. What is Ethernet?

Ethernet is a multiple-access network, meaning that a set of nodes send and receive

frames over a shared link.

4. Define the term carrier sense in CSMA/CD?

All the nodes can distinguish between idle and a busy-link and “collision detect” means

that a node listens as it transmits and can therefore detect when a frame it is transmitting has interfered (collided) with a frame transmitted by another node.

5. Define Repeater?

A repeater is a device that forwards digital signals, much like an amplifier forwards analog signals. However, no more than four repeaters may be positioned between any pairs of hosts, meaning that an Ethernet has a total reach of only 2,500m.

6. Define collision detection?

In Ethernet, all these hosts are competing for access to the same link, and as a consequence, they are said to be in the same collision detection.

7. Why Ethernet is said to be a I-persistent protocol?

An adaptor with a frame to send transmits with probability ‘1 ‘whenever a busy line goes idle.

8. What is exponential back off?

Once an adaptor has detected a collision and stopped its transmission, it waits a certain amount of time and tries again. Each time it tries to transmit but fails, the adaptor doubles the amount of time it waits before trying again. This strategy of doubling the delay interval between each transmission attempt is a general technique known as exponential back off.

9. What is token holding time (THT)?

It defines that how much data a given node is allowed to transmit each time it possesses the token or equivalently, how long a given node is allowed to hold the token.

10. What are the two classes of traffic in FDDI?

• Synchronous

• Asynchronous

11. What are the four prominent wireless technologies?

• Bluetooth

• Wi-Fi(formally known as 802.11)

• WiMAX(802.16)

• Third generation or 3G cellular wireless.

12. Define Bluetooth?

Bluetooth fills the niche of very short-range communication between mobile phones,

PDAs, notebook computers, and other personal or peripheral devices. For example, Bluetooth can be used to connect mobile phones to a headset, or a notebook computer to a printer.

13. What are the four steps involves in scanning?

1. The node sends a Probe frame.

2. All APs within reach reply with a Probe Response frame.

3. The node selects one of the access points, and sends that AP an Association

Request frame.

4. The AP replies with an Association Response frame.

14. Explain the term handoff?

If the phone is involved in a call at the time , the call must be transferred to the new

base station in what is called a hand off.

15. Define satphones?

Satphones use communication satellites as base stations, communicating on frequency

bands that have been reserved internationally for satellite use.

16. How to mediate access to a shared link?

Ethernet,token ring, and several wireless protocols. Ethernet and token ring media

access protocols have no central arbitrator of access. Media access in wireless networks is made more complicated by the fact that some nodes may be hidden from each other due to range limitations of radio transmission.

17. Define Aggregation points?

It collects and processes the data they receive from neighboring nodes, and then

transmit the processed data. By processing the data incrementally, instead of forwarding all the raw data to the base station, the amount of traffic in the network is reduced.

18. Define Beacons?

Beacon to determine their own absolute locations based on GPS or manual configuration. The majority of nodes can then derive their absolute location by combining an estimate of their position relative to the beacons with the absolute location information provided by the beacons.

19. What is the use of Switch?

It is used to forward the packets between shared media LANs such as Ethernet. Such switches are sometimes known by the obvious name of LAN switches.

20. Explain Bridge?

It is a collection of LANs connected by one or more bridges is usually said to form an extended LAN. In their simplest variants, bridges simply accept LAN frames on their inputs and forward them out on all other outputs.

21. What is Spanning tree?

It is for the bridges to select the ports over which they will forward frames.

22. What are the three pieces of information in the configuration messages?

1. The ID for the bridge that is sending the message.

2. The ID for what the sending bridge believes to the root bridge.

3. The distance, measured in hops, from the sending bridge to the root bridge.

23. What is broadcast?

Broadcast is simple – each bridge forwards a frame with a destination broadcast address

out on each active (selected) port other than the one on which the frame was received.

24. What is multicast?

It can be implemented with each host deciding for itself whether or not to accept the

message.

25. How does a given bridge learn whether it should forward a multicast frame over a given port?

It learns exactly the same way that a bridge learns whether it should forward a unicast frame over a particular port- by observing the source addresses that it receives over that port.


UNIT-III

1. Define packet switching?

A packet switch is a device with several inputs and outputs leading to and from the

hosts that the switch interconnects.

2. What is a virtual circuit?

A logical circuit made between the sending and receiving computers. The connection is

made after both computers do handshaking. After the connection, all packets follow the same route and arrive in sequence.

3. What are data grams?

In datagram approach, each packet is treated independently from all others. Even when one packet represents just a place of a multi packet transmission, the network treats it although it existed alone. Packets in this technology are referred to as datagram.

4. What is meant by switched virtual circuit?

Switched virtual circuit format is comparable conceptually to dial-up line in circuit

switching. In this method, a virtual circuit is created whenever it is needed and exits only for the duration of specific exchange.

5. What is meant by Permanent virtual circuit?

Permanent virtual circuits are comparable to leased lines in circuit switching. In this method, the same virtual circuit is provided between two uses on a continuous basis. The circuit is dedicated to the specific uses.

6. What are the properties in star topology?

• Even though a switch has a fixed number of inputs and outputs, which limits the

number of hosts that can be connected to a single switch , large networks can be built by interconnecting a number of switches.

• We can connect switches to each other and to hosts using point-to point links, which typically means that we can build networks of large geographic scope.

7. What is VCI?

A Virtual Circuit Identifier that uniquely identifies the connection at this switch, and which will be carried inside the header of the packets that belongs to this connection.

8. What is hop-by-hop flow control?

Each node is ensured of having the buffers it needs to queue the packets that arrive on that circuit. This basic strategy is usually called hop-by-hop flow control.

9. Explain the term best-effort?

If something goes wrong and the packet gets lost, corrupted, misdelivered, or in any way fails to reach its intended destination, the network does nothing.

10. What is maximum transmission unit?

MTU- which is the largest IP datagram that it can carry in a frame .

11. Define Routing?

It is the process of building up the tables that allow thwe collect output for a packet to

be determined.

12. Define ICMP?

Internet Control Message Protocol is a collection of error messages that are sent back to

the source host whenever a router or host is unable to process an IP datagram successfully

13. Write the keys for understanding the distance vector routing?

The three keys for understanding the algorithm are,

• Knowledge about the whole networks

• Routing only to neighbors

• Information sharing at regular intervals

14. Write the keys for understanding the link state routing?

The three keys for understanding the algorithm are,

• Knowledge about the neighborhood.

• Routing to all neighbors.

• Information sharing when there is a range.

15. How the packet cost referred in distance vector and link state routing?

In distance vector routing, cost refer to hop count while in case of link state routing,

cost is a weighted value based on a variety of factors such as security levels, traffic or the state of the link.

16. Define Reliable flooding?

It is the process of making sure that all the nodes participating in the routing protocol get a copy of the link state information from all the other nodes.

17. What are the features in OSPF?

• Authentication of routing messages.

• Additional hierarchy.

• Load balancing.

18. Define Sub netting?

Subnetting provides an elegantly simple way to reduce the total number of network numbers that are assigned. The idea is to take a single IP network number and allocate the IP address with that network to several physical networks, which are now referred to as subnets.

19. What are the different types of AS?

• Stub AS

• Multi homed AS

• Transit AS

20. What is an Area?

An Area is a set of routers that are administratively configured to exchange link-state information with each other. There is one special area- the backbone area, also known as area

0.

21. What is Source Specific Multicast?

SSM , a receiving host specifies both a multicast group and a specific host .the

receiving host would then receive multicast addressed to the specified group, but only if they are from the special sender.

22. What is meant by congestion?

Congestion in a network occurs if user sends data into the network at a rate greater than that allowed by network resources.

23. Why the congestion occurs in network?

Congestion occurs because the switches in a network have a limited buffer size to store arrived packets.

24. What are the rules of non boundary-level masking?

• The bytes in the IP address that corresponds to 255 in the mask will be repeated in the sub network address

• The bytes in the IP address that corresponds to 0 in the mask will change to 0 in the sub network address

• For other bytes, use the bit-wise AND operator.

25. What is LSP?

In link state routing, a small packet containing routing information sent by a router to

all other router by a packet called link state packet.

1. Explain the main idea of UDP?


UNIT-IV

The basic idea is for a source process to send a message to a port and for the destination process to receive the message from a port.

2. What are the different fields in pseudo header

Protocol number

• Source IP address

• Destination IP addresses.

3. Define TCP?

TCP guarantees the reliable, in order delivery of a stream of bytes. It is a full-duplex

protocol, meaning that each TCP connection supports a pair of byte streams, one flowing in each direction.

4. Define Congestion Control?

It involves preventing too much data from being injected into the network, thereby causing switches or links to become overloaded. Thus flow control is an end to an end issue, while congestion control is concerned with how hosts and networks interact.

5. State the two kinds of events trigger a state transition?

• A segment arrives from the peer.

• The local application process invokes an operation on TCP.

6. What is meant by segment?

At the sending and receiving end of the transmission, TCP divides long transmissions into smaller data units and packages each into a frame called a segment.

7. What is meant by segmentation?

When the size of the data unit received from the upper layer is too long for the network layer datagram or data link layer frame to handle, the transport protocol divides it into smaller usable blocks. The dividing process is called segmentation.

8. What is meant by Concatenation?

The size of the data unit belonging to single sessions are so small that several can fit

together into a single datagram or frame, the transport protocol combines them into a single data unit. The combining process is called concatenation.

9. What is rate based design?

Rate- based design, in which the receiver tells the sender the rate-expressed in either bytes or packets per second – at which it is willing to accept incoming data.

10. Define Gateway.

A device used to connect two separate networks that use different communication protocols.

11. What is meant by quality of service?

The quality of service defines a set of attributes related to the performance of the connection. For each connection, the user can request a particular attribute each service class is associated with a set of attributes.

12. What are the two categories of QoS attributes?

The two main categories are,

• User Oriented

• Network Oriented

13. List out the user related attributes?

User related attributes are SCR – Sustainable Cell Rate PCR – Peak Cell Rate MCR- Minimum Cell Rate CVDT – Cell Variation Delay Tolerance.

14. What are the networks related attributes?

The network related attributes are, Cell loss ratio (CLR) Cell transfer delay (CTD) Cell delay variation (CDV) Cell error ratio (CER).

15. What is RED?

Random Early Detection in each router is programmed to monitor its own queue length and when it detects that congestion is imminent, to notify the source to adjust its congestion window.

16. What are the three events involved in the connection?

For security, the transport layer may create a connection between the two end ports. A

connection is a single logical path between the source and destination that is associated with all packets in a message. Creating a connection involves three steps:

• Connection establishment

• Data transfer

• Connection release


UNIT-V

1. What is the function of SMTP?

The TCP/IP protocol supports electronic mail on the Internet is called Simple Mail

Transfer (SMTP). It is a system for sending messages to other computer users based

on e-mail addresses. SMTP provides mail exchange between users on the same or different computers.

2. What is the difference between a user agent (UA) and a mail transfer agent (MTA)?

The UA prepares the message, creates the envelope, and puts the message in the envelope. The MTA transfers the mail across the Internet.

3. How does MIME enhance SMTP?

MIME is a supplementary protocol that allows non-ASCII data to be sent through

SMTP. MIME transforms non-ASCII data at the sender site to NVT ASCII data and deliver.

it to the client SMTP to be sent through the Internet. The server SMTP at the receiving side receives the NVT ASCII data and delivers it to MIME to be transformed back to the original data.

4. Why is an application such as POP needed for electronic messaging?

Workstations interact with the SMTP host, which receives the mail on behalf of every

host in the organization, to retrieve messages by using a client-server protocol such as Post Office Protocol, version 3(POP3). Although POP3 is used to download messages from the server, the SMTP client still needed on the desktop to forward messages from the workstation user to its SMTP mail server.

6. What is the purpose of Domain Name System?

name.

Domain Name System can map a name to an address and conversely an address to

7. Discuss the three main division of the domain name space.

Domain name space is divided into three different sections: generic domains, country

domains & inverse domain.

clip_image001Generic domain: Define registered hosts according to their generic behavior, uses generic

suffixes.

Country domain: Uses two characters to identify a country as the last suffix.

Inverse domain: Finds the domain name given the IP address.

8. Discuss the TCP connections needed in FTP.

FTP establishes two connections between the hosts. One connection is used for data

transfer, the other for control information. The control connection uses very simple rules of communication. The data connection needs more complex rules due to the variety of data types transferred.

9. Discuss the basic model of FTP.

The client has three components: the user interface, the client control process, and the

client data transfer process. The server has two components: the server control process and the server data transfer process. The control connection is made between the control processes. The data connection is made between the data transfer processes.

10. Name four factors needed for a secure network?

Privacy: The sender and the receiver expect confidentiality.

Authentication: The receiver is sure of the sender’s identity and that an imposter has not sent the message.

Integrity: The data must arrive at the receiver exactly as it was sent.

Non-Reputation: The receiver must able to prove that a received message came from a

specific sender.

11. How is a secret key different from public key?

In secret key, the same key is used by both parties. The sender uses this key and an

encryption algorithm to encrypt data; the receiver uses the same key and the corresponding decryption algorithm to decrypt the data. In public key, there are two keys: a private key and a public key. The private key is kept by the receiver. The public key is announced to the public.

12. What is a digital signature?

Digital signature is a method to authenticate the sender of a message. It is similar to that

of signing transactions documents when you do business with a bank. In network transactions, you can create an equivalent of an electronic or digital signature by the way you send data.

13. What are the advantages & disadvantages of public key encryption?

Advantages:

a) Remove the restriction of a shared secret key between two entities. Here each

entity can create a pair of keys, keep the private one, and publicly distribute the other one.

b) The no. of keys needed is reduced tremendously. For one million users to communicate, only two million keys are needed.

Disadvantage:

If you use large numbers the method to be effective. Calculating the cipher text using the long keys takes a lot of time. So it is not recommended for large amounts of text.

14. What are the advantages & disadvantages of secret key encryption?

Advantage:

Secret Key algorithms are efficient: it takes less time to encrypt a message. The

reason is that the key is usually smaller. So it is used to encrypt or decrypt long messages.

Disadvantages:

a) Each pair of users must have a secret key. If N people in world want to use

this method, there needs to be N (N-1)/2 secret keys. For one million people to communicate, a half-billion secret keys are needed.

b) The distribution of the keys between two parties can be difficult.

15. Define permutation.

Permutation is transposition in bit level.

clip_image002Straight permutation: The no. of bits in the input and output are preserved. Compressed permutation: The no. of bits is reduced (some of the bits are dropped).

Expanded permutation: The no. of bits is increased (some bits are repeated).

16. Define substitution & transposition encryption?

. Substitution: A character level encryption in which each character is replaced by another character in the set.

Transposition: A Character level encryption in which the characters retain their plaintext but the position of the character changes.

17. Define CGI?

. CGI is a standard for communication between HTTP servers and executable programs. It is used in crating dynamic documents.

18. What are the requests messages support SNMP and explain it?

• GET

• SET

The former is used to retrieve a piece of state from some node and the latter is used to store a new piece of state in some node.

19. Define PGP?

Pretty Good Privacy is used to provide security for electronic mail. It provides authentication, confidentiality, data integrity, and non repudiation.

20. Define SSH?

Secure Shell is used to provide a remote login, and used to remotely execute commands and transfer files and also provide strong client/server authentication / message integrity.