__For downloading the complete solution click on the following link__

2. In order that a code is error correcting, the minimum Hamming distance should be :

(A) t

(B) 2t - 1

(C) 2t

(D) 2t + 1

Ans:-D

Explanation:- The error-detecting and error-correcting properties of a block ode depend on its hamming distance.

To reliably DETECT ’t’ errors, you need a distance t+1 code.

To CORRECT t errors, you need a distance 2t+1 code.

9. With four programs in memory and with 80% average I/O wait, the CPU utilisation is?

(A) 60%

(B) 70%

(C) 90%

(D) 100%

Ans:-A

Explanation:-CPU utilisation is given by the formula

= 1 - P pow n

CPU utilisation is calculated from a probabilistic viewpoint. P stands for the fraction of time waiting for I/O to complete.

Number of processes in memory = n

The probability that all n processes are waiting for I/O is p pow n.

P=80%=80/100=0.8

n=4

CPU Utilization = 1 - p pow n

= 1 - (0.8) pow 4

= 1 - 0.4096

= 60%

28.A binary tree is said to have heap property if the elements along any path:

(A) from leaf to root are non-increasing

(B) from leaf to root are non-decreasing

(C) from root to leaf are non-decreasing

(D) from root to leaf are non-increasing

Ans:- D

Explanation:-Answer is in Schaum’s series book on Data structures with C++.

A binary tree is said to have the heap property if the elements along any path from root to leaf are non increasing. A heap is a complete binary tree that has the heap property. So the correct option is D.

33. In which addressing mode the operand is given explicitly in the instruction itself?

(A) Absolute mode

(B) Immediate mode

(C) Indirect mode

(D) Index mode

Ans:- B

Explanation:- In immediate addressing mode, the operand is given in the instruction itself.

Eg:- MOV AL,64H Move 64H to Al register

MOV Bx,0493H Move 0493H to Bx register.

42. Which of the following is used for test data generation?

(A) White box

(B) Black box

(C) Boundary-value analysis

(D) All of the above

Ans:-C

Explanation:- Boundary value analysis is a technique for test data selection.A test engineer chooses values that lie along data extremes.

Hi readers,

I have uploaded the solutions for June 2012 - Paper III. This was particularly difficult because the questions were a bit vague and it was a challenge to solve it. I have solved upto 30 questions in this file. I will be follow it up with the rest of the questions soon . I have tried explaining the solution to each and every question as much as I can. Since the explanations are quite lengthy for most of the questions, reading through this itself will be too exhaustive and time consuming. I suggest you go through the explanation multiple times so that they can be applied in some other situation as well. Once again happy learning....

Download June 2012 - Paper III solved....

Hi friends,

Instead of going through each and every post of mine for getting the solutions for all the questions in a particular paper, I have created the following link for downloading the solution file straightaway. I will keep updating you with more solution files in the coming days. Till then, happy downloading and happy learning.

Please find the downloadable files for the solution of previous year UGC Net papers along with elaborate explanation wherever required.

I will be adding new files for download often. So please keep checking this page....

1. June 2012 - Paper II solved

2. December 2010-Paper II solved

3. December 2011-Paper II solved

4. December 2009 - Paper II solved

5. December 2008 - Paper II solved

6. June 2012 - Paper III solved (partially)

7. June 2009 - PAPER II solved

Look forward to more download links....

This post gives the question and answer for the subject FINITE AUTOMATA from all the previous year question papers of UGC NET.

First the year in which the question appears would be mentioned followed by the question and its answer.

3. Identify the language which is not context - free.

(A) L={wwR|w is a member of {0,1}*}

(B) L={a^{n}b^{n}|n>=0}

(C )L={ww|w is a member of {0,1}*}

(D) L={a^{n}b^{m}c^{m}d^{n}|n,m>=0}

5. Regular expression a+b denotes the set :

(A) {a}

(B) {Epsilon, a, b}

(C) {a, b}

(D) None of these

S → OA, A → 1A/0A/1

(A) 01100

(B) 00101

(C ) 10011

(D) 11111

7. The logic of pumping lemma is a good example of :

(A) pigeon hole principle

(B) recursion

(C) divide and conquer technique

(D) iteration

First the year in which the question appears would be mentioned followed by the question and its answer.

**DECEMBER 2004**

1. The context-free languages are closed for :

(i) Intersection (ii) Union

(iii) Complementation (iv) Kleene Star

then

(A) (i) and (iv) (B) (i) and (iii)

(C ) (ii) and (iv) (D) (ii) and (iii)

**Ans:-C**

**Explanation:-**
Context-free languages are closed under union,intersection and star-closure. Context-free languages are not closed under intersection and complementation.

**June - 2005**

2. Which of the following is not true ?

(A) Power of deterministic automata is equivalent to power of non-deterministic
automata.

(B) Power of deterministic pushdown automata is equivalent to power of
non-deterministic pushdown automata.

(C) Power of deterministic turing machine is equivalent to power of non-deterministic

turing machine.
(D) All the above

**Ans:-B**

**Explanation:-**
Deterministic and nondeterministic finite automata have equivalent computational capabilities.

Deterministic and nondeterministic Turing machines have the same computational capabilities.

However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata. So, the answer is B.

3. Identify the language which is not context - free.

(A) L={wwR|w is a member of {0,1}*}

(B) L={a

(C )L={ww|w is a member of {0,1}*}

(D) L={a

**Ans:-B**

**December 2005**

4. Which sentence can be generated by S → d/bA, A → d/ccA :

(A) bccddd

(B) aabccd

(C) ababccd

(D) abbbd

**Ans:-A**

**Explanation:-**
The most closest answer seems to be A only. The terminals in the grammar are d,b and c. There is no terminal 'a' at all. So the options B,C and D are ruled out. option A can also be derived at something like this.

S->bA

->bccA

->bccccA

->bccccd

So the sentence generated should be bccccd. If there are any other explanations for the same please post them.

5. Regular expression a+b denotes the set :

(A) {a}

(B) {Epsilon, a, b}

(C) {a, b}

(D) None of these

**Ans:-C**

**June 2006**

S → OA, A → 1A/0A/1

(A) 01100

(B) 00101

(C ) 10011

(D) 11111

**Ans:-B**

**Explanation:-**
Non terminals in the above grammar are S, and A. Terminals are 0 and 1. The start symbol of the grammar is S.
S->0A. So rule out strings beginning with 1. so that leaves us with two options A and B.
S->0A

->00A

->001A

->0010A

->00101

So the option B is correct. If you try to derive the string for option A you would not be able to get it. So, the correct answer is option A.

7. The logic of pumping lemma is a good example of :

(A) pigeon hole principle

(B) recursion

(C) divide and conquer technique

(D) iteration

**Ans:-A**

**December - 2006**

8. Which of the regular expressions corresponds to this grammar ? S → AB/AS, A → a/aA, B → b

(A) aa*b+

(B) aa*b

(C ) (ab)*

(D) a(ab)*

**Ans:-B**

**JUNE 2007**

9. The regular expression given below describes :

r=(1+01)*(0+λ)

(A) Set of all string not containing '11'

(B) Set of all string not containing '00'

(C) Set of all string containing '01'

(D) Set of all string ending in '0'

**Ans:-B**

**Explanation:-**

The meaning of (1+01)* means that the set of strings of 1 and 01 of any length including the NULL string. (0+λ) means either 0 or λ. So the full regular expression stands for the set of strings of 1's and 01's of any length ending with 0 or λ. So we cannot say the string will only end in '0'. It could end in λ also. The string can begin with 1 or 01 and multiple times it can get repeated.But the string '11' cannot be together. So the option could be B.

21. A* algorithm uses f' = g + h' to estimate the cost of getting from the initial state to the goal state, where g is a measure of the cost of getting from initial state to the current node and the function h' is an estimate of the cost of getting from the current node to the goal state. To find a path involving the fewest number of steps, we should set

(A) g=1

(B) g=0

(C) h'=0

(D) h'=1

22. The transform which possesses the highest ‘energy compaction’ property is

(A) Slant transform

(B) Cosine transform

(C) Fourier transform

(D) Karhunen-Loeve transform

23. Which one of the following prolog programs correctly implement “if G succeeds then execute goal P else execute goal θ ?”

(A) if-else (G, P, θ) :- !, call(G), call(P). if-else (G, P, θ) :- call(θ).

(B) if-else (G, P, θ) :- call(G), !, call(P). if-else (G, P, θ) :- call(θ).

(C) if-else (G, P, θ) :- call(G), call(P), !. if-else (G, P, θ) :- call(θ).

(D) All of the above

24. The _______ memory allocation function modifies the previous allocated space.

(A) calloc( )

(B) free()

(C) malloc( )

(D) realloc()

25. Which is not the correct statement(s) ?

(i) Every context sensitive language is recursive.

(ii) There is a recursive language that is not context sensitive.

(A) (i) is true, (ii) is false.

(B) (i) is true and (ii) is true.

(C) (i) is false, (ii) is false.

(D) (i) is false and (ii) is true.

26. The mechanism that binds code and data together and keeps them secure from outside world is known as

(A) Abstraction

(B) Inheritance

(C) Encapsulation

(D) Polymorphism

27. Identify the addressing modes of below instructions and match them :

(a) ADI (1) Immediate addressing

(b) STA (2) Direct addressing

(C )CMA (3) Implied addressing

(d) SUB (4) Register addressing

(A) a-1,b-2,c-3,d-4

(B) a-2,b-1,c-4,d-3

(C ) a-3,b-2,c-1,d-4

(D) a-4,b-3,c-2,d-1

28. Which one of the following is not a Greibach Normal form grammar ?

(i) S → a | bA | aA | bB

A→a B→b

(ii) S→a|aA|AB

A→a

B→b

(iii) S→a|A|aA

A→a

(A) (i) and (ii)

(B) (i) and (iii)

(C) (ii) and (iii)

(D) (i), (ii) and (iii)

29. Which of the following IP address class is a multicast address ?

(A) Class A

(B) Class B

(C) Class C

(D) Class D

30. While unit testing a module, it is found that for a set of test data, maximum 90% of the code alone were tested with a probability of success 0.9. The reliability of the module is

(A) atleast greater than 0.9

(B) equal to 0.9

(C) atmost 0.81

(D) atleast 1/0.81

(A) g=1

(B) g=0

(C) h'=0

(D) h'=1

**Ans:-A**

22. The transform which possesses the highest ‘energy compaction’ property is

(A) Slant transform

(B) Cosine transform

(C) Fourier transform

(D) Karhunen-Loeve transform

**Ans:-D**

23. Which one of the following prolog programs correctly implement “if G succeeds then execute goal P else execute goal θ ?”

(A) if-else (G, P, θ) :- !, call(G), call(P). if-else (G, P, θ) :- call(θ).

(B) if-else (G, P, θ) :- call(G), !, call(P). if-else (G, P, θ) :- call(θ).

(C) if-else (G, P, θ) :- call(G), call(P), !. if-else (G, P, θ) :- call(θ).

(D) All of the above

**Ans:-B**

**Explanation:-**
The syntax of If--then---else in prolog goes the following way…

(A->B;C) :-

call(A),

!,

call(B)

(A->B;C) :-

call(C )

So according to the above syntax option B is correct.

24. The _______ memory allocation function modifies the previous allocated space.

(A) calloc( )

(B) free()

(C) malloc( )

(D) realloc()

**Ans:-D**

25. Which is not the correct statement(s) ?

(i) Every context sensitive language is recursive.

(ii) There is a recursive language that is not context sensitive.

(A) (i) is true, (ii) is false.

(B) (i) is true and (ii) is true.

(C) (i) is false, (ii) is false.

(D) (i) is false and (ii) is true.

**Ans:-B**

26. The mechanism that binds code and data together and keeps them secure from outside world is known as

(A) Abstraction

(B) Inheritance

(C) Encapsulation

(D) Polymorphism

**Ans:-C**

27. Identify the addressing modes of below instructions and match them :

(a) ADI (1) Immediate addressing

(b) STA (2) Direct addressing

(C )CMA (3) Implied addressing

(d) SUB (4) Register addressing

(A) a-1,b-2,c-3,d-4

(B) a-2,b-1,c-4,d-3

(C ) a-3,b-2,c-1,d-4

(D) a-4,b-3,c-2,d-1

**Ans:- A**

**Explanation:-**
The instruction ADI adds some content to the accumulator. It is an immediate addressing mode instruction.

The instruction STA stores the contents of the accumulator in the particular memory location specified as operand.

CMA instruction takes complement of the contents of the accumulator.

SUB instruction subtracts the contents of the register to the contents of the accumulator.

. So the option is A.

28. Which one of the following is not a Greibach Normal form grammar ?

(i) S → a | bA | aA | bB

A→a B→b

(ii) S→a|aA|AB

A→a

B→b

(iii) S→a|A|aA

A→a

(A) (i) and (ii)

(B) (i) and (iii)

(C) (ii) and (iii)

(D) (i), (ii) and (iii)

**Ans:-C**

**Explanation:-**
Restriction for GNF:-

The first symbol on the right hand side of the production must be a terminal. It can be followed by zero or more variables. In grammar (ii) of the question, S->AB is a production. AB are two non-terminals and it can be in GNF. In grammar (iii) S->A is given and it is a unit production and that is not allowed in GNF. So the grammar which is not in GNF is (ii) and (iii). So the option is C.

29. Which of the following IP address class is a multicast address ?

(A) Class A

(B) Class B

(C) Class C

(D) Class D

**Ans:-D**

30. While unit testing a module, it is found that for a set of test data, maximum 90% of the code alone were tested with a probability of success 0.9. The reliability of the module is

(A) atleast greater than 0.9

(B) equal to 0.9

(C) atmost 0.81

(D) atleast 1/0.81

**Ans:-C**

18. Consider a schema R(A, B, C, D) and functional dependencies A → B and C → D. Then the decomposition R1(A, B) and R2(C, D) is

(A) Dependency preserving but not lossless join

(B) Dependency preserving and lossless join

(C) Lossless Join but not dependency preserving

(D) Lossless Join

19. The quantiser in an image-compression system is a

(A) lossy element which exploits the psychovisual redundancy

(B) lossless element which exploits the psychovisual redundancy

(C) lossy element which exploits the statistical redundancy

(D) lossless element which exploits the statistical redundancy

20. Data Warehouse provides

(A) Transaction Responsiveness

(B) Storage, Functionality Responsiveness to queries

© Demand and supply Responsiveness

(D) None of the above

(A) Dependency preserving but not lossless join

(B) Dependency preserving and lossless join

(C) Lossless Join but not dependency preserving

(D) Lossless Join

Ans:-A

**Explanation:-**

I have given the explanation in question no. 17 of December 2010 UGC paper. I am repeating it once again here for dependency preservation and lossless join. First of all let us consider the dependency preservation and how to understand it.

Definition of Dependency preservation decomposition:-

Each FD specified in F either appears directly in one of the relations in the decomposition, or be inferred from FDs that appear in some relation.

Let us consider the above example for Dependency preservation

Let R be a relation R(A B C D)

Let there be 2 functional dependencies.

FD1: A->B

FD2: C->D

Let the relation R be decomposed into two more relations.

R1(A B ) : R2(C D)

Let us first consider the relation R1(A B ). Here between A and B the functional dependency FD1 is preserved.

Let us now consider the second relation R2(C D). Between C and D the FD, FD2 is preserved. So in the two relations R1 and R2, all the 2 functional dependencies are preserved.

Now for the lossless join.

A decomposition of R into R1 and R2 is lossless join if and only if at least one of the following dependencies is in F*:
R1 ∩ R2 -> R1
R1 ∩ R2 -> R2
In the above example, R1 ∩ R2 = { null }. So, it is not a lossless join. So the answer is dependency preserving but not lossless join. So, the answer is option A.

19. The quantiser in an image-compression system is a

(A) lossy element which exploits the psychovisual redundancy

(B) lossless element which exploits the psychovisual redundancy

(C) lossy element which exploits the statistical redundancy

(D) lossless element which exploits the statistical redundancy

Ans:-A

20. Data Warehouse provides

(A) Transaction Responsiveness

(B) Storage, Functionality Responsiveness to queries

© Demand and supply Responsiveness

(D) None of the above

Ans:-B

11. X.25 is ________ Network.

(A) Connection Oriented Network

(B) Connection Less Network

(C) Either Connection Oriented or Connection Less

(D) Neither Connection Oriented nor Connection Less

12. Which of the following can be used for clustering of data ?

(A) Single layer perception

(B) Multilayer perception

(C) Self organizing map

(D) Radial basis function

13. Which of the following is scheme to deal with deadlock ?

(A) Time out

(B) Time in

(C) Both (A) & (B)

(D) None of the above

14. If the pixels of an image are shuffled then the parameter that may change is

(A) Histogram

(B) Mean

(C) Entropy

(D) Covariance

15. The common property of functional language and logical programming language :

(A) Both are declarative

(B) Both are based on λ-calculus

(C) Both are procedural

(D) Both are functional

16. Given the following statements :

(i) The power of deterministic finite state machine and non- deterministic finite state machine are same.

(ii) The power of deterministic pushdown automaton and non- deterministic pushdown automaton are same.

Which of the above is the correct statement(s) ?

(A) Both (i) and (ii)

(B) Only (i)

(C) Only (ii)

(D) Neither (i) nor (ii)

17. LetQ(x,y)denote “x+y=0” and let there be two quantifications given as

(i) ∃y∀x Q(x, y)

(ii) ∀x∃y Q(x, y)

where x & y are real numbers. Then which of the following is valid ?

￼(A) (i) is true & (ii) is false.

(B) (i) is false & (ii) is true.

(C) (i) is false & (ii) is also false.

(D) both (i) & (ii) are true.

(A) Connection Oriented Network

(B) Connection Less Network

(C) Either Connection Oriented or Connection Less

(D) Neither Connection Oriented nor Connection Less

**Ans:-A**

**Explanation:-**

X.25 is a connection oriented protocol.

12. Which of the following can be used for clustering of data ?

(A) Single layer perception

(B) Multilayer perception

(C) Self organizing map

(D) Radial basis function

**Ans:-C**

13. Which of the following is scheme to deal with deadlock ?

(A) Time out

(B) Time in

(C) Both (A) & (B)

(D) None of the above

**Ans:-A**

14. If the pixels of an image are shuffled then the parameter that may change is

(A) Histogram

(B) Mean

(C) Entropy

(D) Covariance

**Ans:-D**

15. The common property of functional language and logical programming language :

(A) Both are declarative

(B) Both are based on λ-calculus

(C) Both are procedural

(D) Both are functional

**Ans:-A**

16. Given the following statements :

(i) The power of deterministic finite state machine and non- deterministic finite state machine are same.

(ii) The power of deterministic pushdown automaton and non- deterministic pushdown automaton are same.

Which of the above is the correct statement(s) ?

(A) Both (i) and (ii)

(B) Only (i)

(C) Only (ii)

(D) Neither (i) nor (ii)

**Ans:-B**

**Explanation:-**

The answer is B. But why is it so?. A very good explanation is given in the book "Theory of computation" by A.A.Puntambekar.

We all know that finite machine is of two types. One is deterministic finite state machine and the other one non deterministic finite state machine. Both these machine accept regular language only. So the power of DFA = NFA. So the first statement is true.

Next comes the question of pushdown automaton and the power of deterministic and non-deterministic being the same. PDA has more power than FA because PDA has a memory and so can accept large class of languages than FA. PDA accepts the language of context free grammar. The power of DPDA is less than NPDA because NPDA accepts a larger class of context free language.

Turing machines can accept a more large class of language. Therefore it is the most powerful computational model. The power of deterministic and non deterministic turing machine is the same.

17. LetQ(x,y)denote “x+y=0” and let there be two quantifications given as

(i) ∃y∀x Q(x, y)

(ii) ∀x∃y Q(x, y)

where x & y are real numbers. Then which of the following is valid ?

￼(A) (i) is true & (ii) is false.

(B) (i) is false & (ii) is true.

(C) (i) is false & (ii) is also false.

(D) both (i) & (ii) are true.

**Ans:-B**

**Explanation:-**

The symbol ∀ is called the universal quantifier. The universal qualification of P(x) is the statement "P(x) for all values x in the universe" which is written as
∀xP(x).

The symbol ∃ is called the existential quantifier and represents the phrase "there exists" or "for some". The existential quantification of P(x) is the statement "P(x) for some values x in the universe which is written as ∃xP(x).

A nested quantifier is one where two quantifiers are nested if one is within the scope of the other.

The order of nested universal quantifiers in a statement without other quantifiers can be changed without changing the meaning of the quantified statement.

The order of nested existential quantifiers in a statement without other quantifiers can be changed without changing the meaning of the quantified statement.

But the order of nested universal and existential quantifier is important. The order cannot be changed without affecting the meaning.

Let us consider the quantification ∀x∃y Q(x, y). The domain is real numbers. Q(x,y) is x+y=0. The quantification can be explained this way. Since the universal quantification comes first, it has to be understood as, for all real numbers x there is a real number y such that x+y=0, which is actually true. We are saying that y is the additive inverse of x.

Now let us consider the quantification ∃y∀x Q(x, y). Since the existential quantification comes first, it has to be understood as there is a real number y such that for all real numbers x, x+y=0 , which is false.

So, the quantification (i) is false and (ii) is true.

Subscribe to:
Posts (Atom)