UGC NET Computer Science July 2018 - II | Question 23

Question 23

---

A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?

Options:

1. (1) 3
2. (2) 4
3. (3) 5
4. (4) 6

Answer : (3) 5

Explanation Question 23

Given:
Hash table has indexed from 0 to 6.
keys are 44, 45, 79, 55, 91, 18, 63
h(key)=key mod 7  ( h(key) value is in range of 0-6 inclusive)

Solution:

Table after inserting 44, 45
h(key)= key mod 7
h(44) = 44 mod 7 = 2
h(45) = 45 mod 7 = 3
44 is placed position 2 and 45 is placed at position 3.

0	1	2	3	4	5	6
-	-	44	45	-	-	-

Table after inserting 79
h(79) = 79 mod 7 = 2
but 2 is already filled by 44, linear probing is applied but 3 is also filled by 45.
To apply linear probing, we check for the next unoccupied position in the table.
So, 79 will occupy 4.

0	1	2	3	4	5	6
-	-	44	45	79	-	-

Table after inserting 55, 91
h(55) = 55 mod 7 = 6
h(91) = 91 mod 7 = 0
55 is placed position 6 and 91 is placed at position 0.

0	1	2	3	4	5	6
91	-	44	45	79	-	55

Table after inserting 18
h(18) = 18 mod 7 = 4
but 4 is occupied by 79 so, it will occupy 5.

0	1	2	3	4	5	6
91	-	44	45	79	18	55

Table after inserting 63
h(63) = 63 mod 7 = 0.
0 is also occupied so, it will occupy 1.

0	1	2	3	4	5	6
91	63	44	45	79	18	55

So, option (3) is correct.

Previous	Next
UGC NET CS 2018 July - II Question 22	UGC NET CS 2018 July - II Question 24

UGC NET Computer Science July 2018 - II Question 17

Question 17

---

17. A software design pattern often used to restrict access to an object is :

Options:

1. (1) adapter
2. (2) decorator
3. (3) delegation
4. (4) proxy

Answer : (4) proxy

Explanation Question 17

• Proxy Pattern → We need the ability to control the access to an object. The light objects are called proxies and they will instantiate those heavy objects when they are really need and by then we'll use some light objects instead.  Use of the proxy can simply be forwarding to the real object or to provide additional logic. A proxy is a Interface or wrapper or agent object. Proxy is being called by the client to access the real object serving behind the scenes. 
  Read more about - Proxy Pattern
• Adapter → Match interface of different classes.
• Decorator → Add responsibilities objects dynamically. Effectively in the instantiation process, object-creation patterns use delegation effectively to get the job done.
• Delegation → In software engineering, the delegation pattern is an object-oriented design pattern that allows object composition to achieve the same code reuse as inheritance. In delegation, an object handles a request by delegating to a second object (the delegate). The delegate is a helper object, but with the original context.

From above definations we conclude that "Proxy is a software design pattern often used to restrict access to an object"

So, Option (4) is correct answer.

Similar Questions:

1. A design pattern used to enhance the functionality of an object is
(a) Adapter
(b) Decorator
(c) Delegation
(d) Proxy

2. A design pattern often used to restrict access to an object is
(a) Adapter
(b) Decorator
(c) Delegation
(d) Proxy

3. You have a class that accepts and returns values in British Imperial units (feet, miles, etc.), but you
need to use metric units. The design pattern that would best solve your problem is
(a) Adapter
(b) Decorator
(c) Delegation
(d) Proxy

Question Reference::https://courses.cs.washington.edu/courses/cse331/18sp/exams/cse331-12sp-final-sol.pdf

Previous	Next
UGC NET CS 2018 July - II Question 16	UGC NET CS 2018 July - II Question 18

UGC NET Computer Science July 2018 - II Question 52

Question 52

---

52. In a paged memory, the page hit ratio is 0.40. The time required to access a page in secondary memory is equal to 120 ns. The time required to access a page in primary memory is 15 ns. The average time required to access a page is ______ .

1. (1) 105
2. (2) 68
3. (3) 75
4. (4) 78

Answer : (4) 78

Explanation Question 52

PAGE HIT = page present in ram or main memory
PAGE MISS = page fault so page swapped from the secondary memory
because we look for a page in secondary memory when the page is not present in the main memory, therefore, we need to add main memory lookup time.

Average access time
= hit ratio * primary memory access time + (1 – hit ratio) * secondary memory access time
Average access time = 0.4 * 15 + 0.6 * 120
Average access time = 6 + 72
Average access time = 78.

So, option (4) is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 51	UGC NET CS 2018 July - II Question 53

UGC NET CS 2018 July - II Question 90

Question 90

---

Which of the following statements is true ?

1. (1) (Z, ≤ ) is not totally ordered
2. (2) The set inclusion relation ⊆ is a partial ordering on the power set of a set S
3. (3) (Z, ≠ ) is a poset
4. (4) The directed graph is not a partial order
   

   

   Diagram for option (4) The directed graph is not a partial order

Answer : (2) The set inclusion relation ⊆ is a partial ordering on the power set of a set S

Explanation Question 90

Options (1) - FALSE
(Z, ≤ ) is not totally ordered
Z = (..., -3, -2, -1, 0, 1, 2, 3, ...}
Show that “less than or equal” relation
is a partial ordering on the set of integers.
– a<=a for every integer a (reflexive)
– a<=b, b<=a, then a=b (anti-symmetric)
– a<=b, b<=c, then a<=c (transitive)
Thus <= is a partial ordering on the set of
integers
(Z,<=) is a poset.

To prove that Z is Totally Ordered Set:
If (S,R) is a poset and every two
elements of S are comparable, S is called
a totally ordered set or linearly ordered
set.

Comparable: The elements a and b of a poset (Z, ≤ )
are comparable, if either aRb or bRa holds.

Option 2: - TRUE
The set inclusion relation ⊆ is a partial ordering on the power set of a set S (TRUE)
let set S = {a,b}
P(S) = {{a} , {b} ,{a,b} , Φ}

Show that  relation (S,⊆) is a partial ordering on the set of integers.
Take any two element from S, lets say s1 and s2
– s1⊆s1 for every element s1 (reflexive)
– s1⊆s2, s2⊆s1, then s1==s2 (anti-symmetric)
– s1⊆s2, s2⊆s3, then s1⊆s3 (transitive)
Thus ⊆ is a partial ordering on the power set of a set S
(S,⊆) is a poset.

Options 3: - FALSE
(Z,≠) is a poset?
Show that (Z,≠) is a partial ordering on the set of integers.
Take any two integers, then
– aRa -> a≠a for every integer a (not reflexive)
Reflexive Relation doesn't satisfy.
So, (Z,≠) is not a poset.

Options 4: - FALSE
Relation set for the directed graph is D={(a,a),(a,b),(b,b)}
Reflecxive,transitive property holds for the elements in the set.
Anti-symattric -> if R(a, b) with a ≠ b, then R(b, a) must not hold, so, Anti-symattric also holds.

References:
Partial Orderings - http://cse.iitkgp.ac.in/~debdeep/courses_iitkgp/FOC/slidespdf/POS.pdf
Partially ordered set - https://en.wikipedia.org/wiki/Partially_ordered_set
Total order - https://en.wikipedia.org/wiki/Total_order

Previous	Next
UGC NET CS 2018 July - II Question 89	UGC NET CS 2018 July - II Question 91

UGC NET CS 2018 July - II Question 77

Question 77

---

77. Consider the following English sentence :
"Agra and Gwalior are both in India".
A student has written a logical sentence for the above English sentence in First-Order Logic using predicate In(x, y), which means x is in y, as follows :
In(Agra, India) ∨ In(Gwalior, India)
Which one of the following is correct with respect to the above logical sentence ?

Options:

1. (1) It is syntactically valid but does not express the meaning of the English sentence.
2. (2) It is syntactically valid and expresses the meaning of the English sentence also.
3. (3) It is syntactically invalid but expresses the meaning of the English sentence.
4. (4) It is syntactically invalid and does not express the meaning of the English sentence.

Answer : (1) It is syntactically valid but does not express the meaning of the English sentence.

Explanation Question 77

Predicate In(Agra, India) means Agra is in india
Predicate In(Gwalior, India) means Gwalior is in india

According to the given english statement "Agra and Gwalior are both in India", both Predicate "In(Agra,India)" and "In(Gwalior,India)" should be true

Therefore use of conjunction as connector requires between both predicates "In(Agra, India) ∧ In(Gwalior, India)".

But given that In(Agra, India) ∨ In(Gwalior, India), in this it uses connector "∨". So, the entire gives the meaning of Either Agra is in india or Gwalior is in india.

So, Logic is not equivalent for given English sentence and given First-Order Logic.
Given predicate "In(Agra, India) ∨ In(Gwalior, India)" is syntactically correct but not represent the given english statement.

So, option 1 is correct answer

Previous	Next
UGC NET CS 2018 July - II Question 76	UGC NET CS 2018 July - II Question 78

UGC NET Computer Science July 2018 - II | Question 76

Question 76

---

76. Consider the following statements :
(a) False ⊨ True
(b) If α ⊨ (β ∧ γ) then α ⊨ β and α ⊨ γ.
Which of the following is correct with respect to the above statements ?

1. (1) Both statement (a) and statement (b) are false.
2. (2) Statement (a) is true but statement (b) is false.
3. (3) Statement (a) is false but statement (b) is true.
4. (4) Both statement (a) and statement (b) are true.

Answer : (4) Both statement (a) and statement (b) are true.

Explanation Question 76

• Statement (a) "False ⊨ True" is TRUE
  A ⊨ B means "A" logically entails "B" if and only if the sentence A ⇒ B is valid.
  We need to prove that False ⇒ True is valid.
  ∴ False ⇒ True is always true
  because we know : (a ⇒ b) ≡ (¬a ∨ b) So, False ⇒ True is equivalent to ( ¬Flase ∨ True ) which is always true.
   
  
• Statement (b) "if α ⊨ (β ∧ γ) then α ⊨ β and α ⊨ γ" is TRUE
  by constructing below truth table you will find out that
  " α ⊨ β and α ⊨ γ " are true for all the cases for which "α ⊨ (β and γ)" is true
   
  

  α	β	γ	(β ∧ γ)	α ⊨ (β ∧ γ)	α ⊨ β	α ⊨ γ
  				¬ α ∨ (β ∧ γ)	¬ α ∨ β	¬ α ∨ γ
  0	0	0	0	1	1	1
  0	0	1	0	1	1	1
  0	1	0	0	1	1	1
  0	1	1	1	1	1	1
  1	0	0	0	0	0	0
  1	0	1	0	0	0	1
  1	1	0	0	0	1	0
  1	1	1	1	1	1	1

Definition of Logical Entailment
A set of sentences (called premises) logically entails a sentence (called a conclusion) if and only if every truth assignment that satisfies the premises also satisfies the conclusion.

Example of Logical Entailment:
“KB logically entails S” if all the models that evaluate KB to True also evaluate S to True.
Denoted by: KB ⊨ S

Reference : Logical Entailment

Reference 1 : Realm world example of Logical Entailment

Reference 2 : https://www.ics.uci.edu/~welling/teaching/271fall09/HW6_sol.pdf#page=8

Previous	Next
UGC NET CS 2018 July - II Question 75	UGC NET CS 2018 July - II Question 77

UGC NET Computer Science July 2018 - II Question 91

Question 91

---

91. CMOS is a Computer Chip on the motherboard, which is :

Options:

1. (1) RAM
2. (2) ROM
3. (3) EPROM
4. (4) Auxillary storage

Answer : (1) RAM

Explanation Question 91

Complementary metal-oxide Semiconductor(CMOS) is a random access memory which stores computer start up information which is used by BIOS. CMOS memory in a computer is a type of non-volatile RAM (NVRAM) that stores BIOS settings and date/time information.

So, Option 1 is correct answer.

Reference 1 : CMOS Applications and Advantages

Reference 2 : CMOS Working Principle and Applications

Previous	Next
UGC NET CS 2018 July - II Question 90	UGC NET CS 2018 July - II Question 92

UGC NET Computer Science 2018 July - II Question 80

Question 80

---

80. Consider the set of all possible five-card poker hands dealt fairly from a standard deck of fifty-two cards. How many atomic events are there in the joint probability distribution ?

Options:

1. 1 2, 598, 960
2. 2 3, 468, 960
3. 3 3, 958, 590
4. 4 2, 645, 590

Answer : (1) 2, 598, 960

Explanation Question 80

Number of atomic events are there in the joint probability distributionof 5 cards hand from a 52 deck of cards is calculated as shown below:

Total number of combinations possible to have a set of 5 cards from 52,

Total atomic events or count = ⁵²C₅
= 52!/5! * (52-5)!
= 52!/5! * 47!
= (48 x 49 x 50 x 51 x 52)/5!
= 311875200/120
= 2598960

So, Option 1 is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 79	UGC NET CS 2018 July - II Question 81

UGC NET CS 2018 July - II Question 96

Question 96

---

96. Perform the following operation for the binary equivalent of the decimal numbers
(−14)₁₀+(−15)₁₀ The solution in 8-bit representation is :

Options:

1. (1) 11100011
2. (2) 00011101
3. (3) 10011101
4. (4) 11110011

Answer : (1) 11100011

Explanation Question 96

(−14)₁₀ + (−15)₁₀ = (-29)₁₀

Value of 29 in binary is 00011101

To get a binary value of -29:

1. We need to take 1’s complement of 00011101 → 11100010
2. Then add 1 to it. i.e. 11100011.

So, option (A) is the correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 95	UGC NET CS 2018 July - II Question 97

UGC NET CS 2018 July - II Question 59

Question 59

---

59. Consider the following three processes with the arrival time and CPU burst time given in milliseconds :

Process	Arrival Time	Burst Time
P1	0	7
P2	1	4
P3	2	8

The Gantt Chart for preemptive SJF scheduling algorithm is _________.

Options:

1. (1)
2. (2)
3. (3)
4. (4)

Answer : (2)

Explanation Question 59

Question asks for Gantt Chart for preemptive SJF

Option (1) is Not preemptive.
P1 continues execution without being preempted when sorter process P2 with Burst time 4 comes.

Option (2) is Preemptive SJF.
Here, P1 executes for 1 second and then preempted by P2 which executes for 4 seconds. Then P1 finishes its remaining execution  followed by execution of P3.

Option (3) is Not preemptive.
Not pre-emptive as P1 continues execution without being preempted when sorter process P2 with Burst time 4 comes. Each of the processes carries on execution without being preempted.

Option (4) is Preemptive but P2 starts execution even before it's arrival time 1.

So, Option (2) is correct answer. 

Previous	Next
UGC NET CS 2018 July - II Question 58	UGC NET CS 2018 July - II Question 60

UGC NET CS 2018 July - II Question 75

Question 75

---

75. Consider a vocabulary with only four propositions A, B, C and D. How many models are there for the following sentence ?
B v C

Options:

1. (1) 10
2. (2) 12
3. (3) 15
4. (4) 16

Answer : (2) 12

Explanation Question 75

We know there are total 2⁴ = 16 cases.
As shown in below truth table, it won't satisfy the condition when B = C = 0.

A	B	C	D	B v C
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

So, from the given sentence false(0) occurs only if B and C are false(0) which occurs 4 times.
Required number of models = 16 - 4 = 12.

Hence, Option (2) is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 74	UGC NET CS 2018 July - II Question 76

UGC NET CS 2018 July - II Question 64

Question 64

---

64. Relations produced from E - R Model will always be in ________.

Options:

1. (1) 1 NF
2. (2) 2 NF
3. (3) 3 NF
4. (4) 4 NF

Answer : (3) 3 NF

Explanation Question 64

Option (3) is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 63	UGC NET CS 2018 July - II Question 65

UGC NET Computer Science July 2018 - II Question 50

Question 50

---

Encrypt the Message “HELLO MY DEARZ” using Transposition Cipher with

Key

{

Plain Text    2 4 1 3 Cipher Text    1 2 3 4

Options:

1. (1) HLLEO YM AEDRZ
2. (2) EHOLL ZYM RAED
3. (3) ELHL MDOY AZER
4. (4) ELHL DOMY ZAER

Answer: (3) ELHL MDOY AZER

Explanation Question 50

Given:
In question encryption of given message using Transposition Cipher with Given message is “HELLO MY DEARZ”
Key - Plain Text -> 2 4 1 3
Key - Cipher Text ->1 2 3 4

Solution:
Step-1: According to key size divide number of character into blocks. Here, key size is 4. So, character block size is 4.
Step-2: Remove the spaces in the given message and write characters in sequential order. Now arrange then in group of 4 as shown in below matrix.

Key
1	2	3	4
H	E	L	L
O	M	Y	D
E	A	R	Z

Step-3: Sort column as per given Plain key as shown in below matrix.

Key
2	4	1	3
E	L	H	L
M	D	O	Y
A	Z	E	R

Read the matrix horizontally one by one row.

Encrypted message will be ELHL MDOY AZER.

So, option (3) is correct.

Previous	Next
UGC NET CS 2018 July - II Question 49	UGC NET CS 2018 July - II Question 51

UGC NET Computer Science July 2018 - II Question 48

Question 48

---

Decrypt the message “WTAAD” using the Caesar Cipher with key = 15.

1. (1) LIPPS
2. (2) HELLO
3. (3) OLLEH
4. (4) DAATW

Answer : (2) HELLO

Explanation Question 48

Caesar Cipher Algorithm Mathematical Description:
First we translate all of our characters to numbers, 'a'=0, 'b'=1, 'c'=2, ... , 'z'=25.
We can now represent the Caesar cipher encryption function, e(x), where x is the character we are encrypting, as:
e(x)=(x+k) (mod 26)

Where k is the key (the shift) applied to each letter.
After applying this function the result is a number which must then be translated back into a letter.
The decryption function is :
d(x)=(x-k) (mod 26)

Solution:

Remember alphabet ordering:
Only remember the alphabets that occur at multiplication of 5:
1 st alphabet -> A  (1)
2 nd alphabet -> E (5)
3 rd alphabet -> J  (10)
4 th alphabet -> O (15)
5 th alphabet -> T (20)
6 th alphabet -> Y (25)

Need to remember word EJOTY
for our case number numbering is E- 4, J-9, O-14, T-19 Y-24

Position of our alphabets:
W -> T+3 -> (19+3) = 22
T -> 19
A -> 1
D -> 3

Decryption of given alphabets:
W -> (22 -15) (mod 26) = 7 ->H
T -> (19 -15) (mod 26) = 4  -> E
A -> (1-15) (mod 26) = -14 +26 -> L
A -> (1-15) (mod 26) = -14 + 26 -> L
D -> (3 -15) (mod 26) = -12 + 26 -> O

In the above, the result is in the range 0 to 25; i.e., if x + n or x − n are not in the range 0 to 25, we have to subtract or add 26.)

We can decrypt the the message "WTAAD" using the Caesar Cipher with key=15 to "HELLO".

So, option (2) is correct answer

Previous	Next
UGC NET CS 2018 July - II Question 47	UGC NET CS 2018 July - II Question 49

UGC NET Computer Science July 2018 - II Question 47

Question 47

---

47. In Challenge-Response authentication the claimant ________.

Options:

1. (1) Proves that she knows the secret without revealing it
2. (2) Proves that she doesn’t know the secret
3. (3) Reveals the secret
4. (4) Gives a challenge

Answer : (1) Proves that she knows the secret without revealing it

Explanation Question 47

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information

Example:

WHAT IS ZERO KNOWLEDGE AUTHENTICATION?

Zero-knowledge authentication is when a prover convinces a verifier that she is in possession of an identifying secret, without revealing the secret itself. One example for zero-knowledge authentication is when a prover has an asymmetric key-pair (e.g. RSA, EC) and using the private key (the identifying secret) to respond to a challenge sent with the public key. The private key is never revealed, but the verifier is convinced that the prover has the key.

Previous	Next
UGC NET CS 2018 July - II Question 46	UGC NET CS 2018 July - II Question 48

UGC NET Computer Science July 2018 - II Question 37

Question 37

---

37. Context sensitive language can be recognized by a :

Options:

1. (1) Finite state machine
2. (2) Deterministic finite automata
3. (3) Non-deterministic finite automata
4. (4) Linear bounded automata

Answer : (4) Linear bounded automata

Explanation Question 11

Unrestricted Grammar: Recognized by Turing machine

Context Sensitive Grammar: Recognized by the Linear Bound Automata

Context Free Grammar: Recognized by a Pushdown automata

Regular Grammar: Accepted by a finite state automaton ( Deterministic finite automata & Non-deterministic finite automata)

So, Option (4) is correct answer.

Theory of Computation - Chomsky Hierarchy

Previous	Next
UGC NET CS 2018 July - II Question 36	UGC NET CS 2018 July - II Question 38

UGC NET Computer Science July 2018 - II Question 36

Question 36

---

Consider the following two Grammars :

G1 : S → SbS|a
G2 : S → aB|ab, A→GAB|a, B→ABb|b

Which of the following option is correct ?

Options:

1. (1) Only G1 is ambiguous
2. (2) Only G2 is ambiguous
3. (3) Both G1 and G2 are ambiguous
4. (4) Both G1 and G2 are not ambiguous

Answer : (3) Both G1 and G2 are ambiguous

Explanation Question 36

Solution:

Both G1 and G2 are ambiguous
As both grammars have two derivations for same string:

G1 : S → SbS|a

Grammer G1 Derivation-1:
S → SbS
        SbSbS
        ababa

Grammer G1 Derivation-2:
S → SbS
SbSbS
ababa


G2 : S → aB|ab, A→AB|a, B→ABb|b

Grammer G2 Derivation-1:
 S → aB
aABb
aABBb
aABABbb
aababbb

Grammer G2 Derivation-2:
S → aB
aABb
aAABbb
aABABbb
aababbb

Both G1 and G2 are ambiguous as both grammars have two derivations for same string as shown in above.

So, Option (3) is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 35	UGC NET CS 2018 July - II Question 37

UGC NET Computer Science July 2018 - II Question 35

Question 35

---

35. To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :

Options:

1. (1) 2n−1
2. (2) 2n
3. (3) n+1
4. (4) n²

Answer : (1) 2n−1

Explanation Question 35

In CNF , the height of the syntax tree is 2n-1 i.e. 2n-1 productions are used to obtain a string on n terminals.

Previous	Next
UGC NET CS 2018 July - II Question 34	UGC NET CS 2018 July - II Question 36

UGC NET Computer Science July 2018 - II Question 34

Question 34

---

34. Pushdown automata can recognize language generated by ______ .

Options:

1. (1) Only context free grammar
2. (2) Only regular grammar
3. (3) Context free grammar or regular grammar
4. (4) Only context sensitive grammar

Answer: (3) Context free grammar or regular grammar

Explanation Question 34

• Turing Machine recognises ALL
• Linear Bounded Automata recognises context sensitive grammar, Context free grammar, regular grammar
• Push down automata recognises Context free grammar, regular grammar
• Finite Automata recognises only regular grammar

So, Push down automata reconize regular as well as context free grammar.

So, Option (3) is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 33	UGC NET CS 2018 July - II Question 35

UGC NET Computer Science July 2018 - II Question 33

Question 33

---

33. A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :

Options:

1. (1) 0
2. (2) 1
3. (3) 1 or more
4. (4) 2 or more

Answer : (4) 2 or more

Explanation Question 33

PDA have only one stack...
with 2 stacks we can implement queue → T(n+2) is sufficient to form Turing Machine.
moreover expressive power of T(n+2) = T(n+3) = T(n+4) etc..
Therefore we need one more extra auxiliary stack memory for PDA or we need atleast 2 auxiliary memory to implement TM

So, Option (4) is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 32	UGC NET CS 2018 July - II Question 34