June 2010 paper 3

Section-A(Elective)-40 marks
TOC-
Q.1
a)Design a TM for a^nb^n c^n.
b)NFA for
    -strings (0,1) with 1 at even places
    -with substrings 000 and 010

Q.2.What is the difference between bit rate and baud rate?For manchester encoding what is the baud rate for 1 mbps?
Given a complete binary tree its inorder is given ACGHBDE.., Find the preorder and postorder.
  OR
Given the relations and Functional dependency,if its decomposed into other relations.Is the dependency preserved and is it lossless?
Given the memory size what is first fit,best fit and worst fit

Section-b(Elective)-Essay Type
Section-C
 Each question carries 10 marks-

 Q.1.What is the role of entities in XML?What are the different types of entities in XML?

 Answer: Entities are variables used to define shortcuts to standard text or special characters.They can be thought of as macros or aliases. 
When you use the entity name elsewhere within a DTD, or in an XML document, language parsers replace the name with the corresponding characters.This helps you avoid typing name everytime.
There are three different types  of entities in XML-
a)Internal Entity:-
   <!Entity UGC "University grant commission">
  The replacement text is stored in the declaration itself.To use this entity you insert an entity reference in your document "&UGC;"
b)External entity:-
   <!Entity course SYSTEM "/standard/course.xml">
   when the replacement text is long then it is placed in some other file.External entities allow an XML document to refer to an external file.They contain either text or binary data(as images).
c)Parameter entity:-is used for shortcuts within the DTD
   <!Entity %name "replacement text">
these entities are identified by placing % instead of &,also for refering " % "is used.
eg
<!ENTITY book "UGC NET: BPB, &#xA9; 1947 %pub; &rights;">

Q.2.Write the function of 8:1 multiplexer for (0,3,4,6,8,9,12,14)
Q.3.Draw a conceptual dependency graph for the statement "Smoking kills...."
Q.4.On what basis does the window make a selection whether a line will be clipped,displayed or discarded.
given the window has bottom  right at (200,50) and top left given and the line points given?
Q.5.For a college an attendence sheet has to be maintained.Which data structure will you use?How would your choice change in the following conditions-
a)the students are 50 to 1000 only in number
b)the students are 10,000 to 50,000 and data is to be maintained centrally.
c)the students are 10,000 to 50,000 and data is to be distributed.
Q.6.Explain with example that Quick Sort is divide and conquer.
Q.7.What are the factors that determine the cost of software maintenance.

Section-D

Given some paragraph-
a)Draw Use case diagram
b)draw Class diagram
c)draw Sequence Diagram
d)draw state diagram
e)draw activity diagram

TOC Sample Paper

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

Ans:
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)]

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

Ans:
(b+c)* c (b+c)* c (b+c)*

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

Ans:
( b* a b* a b* a b*)*

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

Ans:
(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,………………………………….}

Q.Reg exp denoting a language over ={1} having
(i)even length of string (ii)odd length of a string
Ans:
(i) Even length of string R=(11)*
(ii) Odd length of the string R=1(11)*

Q.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’

Ans:
(i)(0+1)* 0101(0+1)*
(ii)11(1+a+b)* ab
(iii)(a+b)* bbb (a+b)*
(iv)(1+01)* (10+11)* 1

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

Ans: R=a+b+

Q. What are the applications of pumping lemma?
Ans:
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.

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

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

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

Ans:
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}

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

Ans: The grammar has the production P as:
S->aAa
A->aAa | b
The grammar is thus : G=( {S,A} ,{a,b} ,P,S)

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

Ans:
G=({S}, {a,b} , P, S )
P:{ S -> aSa ,
S-> b S b,
S-> a,
S->b,
S-> } which is in palindrome.

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

Ans:
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 }

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

Ans :
S-> , is in L(G)
S-> 0S1 =>0 1=>01
S->0S1=>0 0S11=>0011
Thus L(G)= { 0n1n | n>=0}

TOC Sample Paper MCQ

Que. 1 Given the following expression grammar:

E->E * F | F+E | F
F-> F-F | id

Which of the following is true?
A * has higher precedence than +
B - has higher precedence than *
C + and - have same precedence
D + has higher precedence than *

Que. 2 Consider the following two statements:

S1: {(O^2n) |n>/=1} is a regu1ar language
S2: {(O^m)(1^n)(O^m+n)|m>/=l and n>/=l} is a regu1ar language

Which of the following statements is correct?
A Only S1 is correct
B Only S2 is correct
C Both S1 and S2 are correct
D None of S1 andS2 is correct

Que. 3 Which of the following statements in true?

A If a language is context free it can always be accepted by a deterministic
push-down automaton
B The union of two context free languages is context free
C The intersection of two context free languages is context free
D The complement of a context free language is context free

Que. 4 Which of the following statements is false?

A An unambiguous grammar has same leftmost and rightmost derivation
B An LL(1) parser is a top-down parser
C LALR is more powerful than SLR
D An ambiguous grammar can never be LR(k) for any k

Que. 5 Consider the following languages:

L1={w w l w (belongs) to) {a,b}*}
L2={ww^R | w (belongs) {a, b}*, w R is the reverse of w}
L3 = { 0^2i | i is an integer}
L4 = {[(O)^i]^2| i is an integer}

Which of the languages are regular?
A Only L1 and L2
B Only L2, L3, and L4
C Only L3 and L4
D Only L3

Que. 6 Context free language are closed under

A union, intesection
B union,kleene closure
C intesection,complement
D complement,kleene closure


Que. 7 Context free languages are

A closed under union
B closed under complementation
C closed under intersection
D all of the above

Que. 8 Which one is equivalent (i) (00)*(e+0) (ii) (00)* (iii) 0* (iv)
0(00)*

A (i) and (ii)
B (ii) and (iii)
C (i) and (iii)
D (iii) and (iv)

Que. 9 Type O grammer is

A (C)both and (b) above
B (C)both (a) and above
C both (a) and (b) above
D none of these

Que. 10 Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

A 8
B 14
C 15
D 48