Aspire Faculty ID #18775 · Topic: UGC NET Computer Science Sep 2022 (Paper II) · Just now
UGC NET Computer Science Sep 2022 (Paper II)

Consider two lists A and B of three strings on $\{0,1\}$X:
List AList B
1111
1011110
100
Y:
List AList B
10101
01111
101011
Which of the following is true?

Solution

PCP means Post Correspondence Problem.

In PCP, we have to choose the same sequence of indices from both lists such that the concatenation of strings from List A and List B becomes exactly equal.

First check list X.

List X pairs are:

$1:(1,111)$

$2:(10111,10)$

$3:(10,0)$

Try the sequence of indices:

$2,1,1,3$

Now concatenate strings from List A:

$10111\cdot 1\cdot 1\cdot 10$

$=101111110$

Now concatenate strings from List B using the same index sequence:

$10\cdot 111\cdot 111\cdot 0$

$=101111110$

Both strings are equal.

So, PCP in X has a solution.

Now check list Y.

List Y pairs are:

$1:(10,101)$

$2:(011,11)$

$3:(101,011)$

A valid PCP solution must start with a pair where the first symbols can match.

Only pair $1$ can start a possible match because:

List A gives $10$

List B gives $101$

Here, List B has one extra $1$ at the end.

So after choosing pair $1$, we have:

List A $=10$

List B $=101$

Now List B is ahead by extra $1$.

To balance it, the next string from List A must start with $1$.

Possible choices are pair $1$ or pair $3$.

If we choose pair $1$ again:

List A $=1010$

List B $=101101$

Here mismatch occurs.

If we choose pair $3$:

List A $=10101$

List B $=101011$

Again List B has extra $1$.

This same situation repeats, and equality is never obtained.

Pair $2$ cannot fix it because its List A string starts with $0$, while the required next symbol should match extra $1$.

Therefore, PCP in Y has no solution.

Hence, only PCP in X has solution.

← Previous Next →

Previous 10 Questions — UGC NET Computer Science Sep 2022 (Paper II)

Nearest first
1
A magnetic tape drive has a transport speed of $200$ inches per second and a recording density of $1600$ bytes per inch…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 2
For the following page reference string $4,3,2,1,4,3,5,4,3,2,1,5$, the number of page faults that occur in the least Re…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 3
A trigger is
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 4
Let $R(ABCDEFGH)$ be a relation schema and $F$ be the set of dependencies$F=\{A\to B,\ ABCD\to E,\ EF\to G,\ EF\to H,\ …
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 5
Consider the following two lists:List IList II(A) Stack overflow(I) Software Interrupt(B) Timer(II) Internal interrupt(…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 6
How many rotations are required during the construction of an AVL tree if the following elements are to be added in the…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 7
Consider the traversal of a treePreorder $\to ABCEIFJDGHKL$Inorder $\to EICFJBGDKHLA$Which of the following is correct …
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 8
Consider the hash table of size $11$ that uses open addressing with linear probing. Let $h(k)=k\mod 11$ be the hash fun…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 9
Which of the following algorithm design approach is used in Quick sort algorithm?
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 10
Consider a B-tree of height $h$ minimum degree $t\ge 2$ that contains any $n$-key, where $n\ge 1$. Which of the followi…
Topic: UGC NET Computer Science Sep 2022 (Paper II)

Next 10 Questions — UGC NET Computer Science Sep 2022 (Paper II)

Ascending by ID
1
Consider the properties of recursively enumerable sets:(A) Finiteness(B) Context Freedom(C) EmptinessWhich of the follo…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 2
Consider the following : List IList II(A) Activation record(I) Linker Loader(B) Location counter(II) Garbage Collection…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 3
 Consider the following related to Fourth Generation Technique $(4GT)$:(A) It controls efforts.(B) It controls res…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 4
Consider the grammar $S\to SbS\mid a$.Consider the following statements:The string $abababa$ has(A) two parse trees(B) …
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 5
In a game playing search tree, upto which depth $\alpha-\beta$ pruning can be applied?(A) Root $(0)$ level(B) $6$ level…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 6
Consider $\alpha,\beta,\gamma$ as logical variables. Identify which of the following represents correct logical equival…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 7
Let $(\{a,b\},*)$ be a semigroup, where $a*a=b$.(A) $a*b=b*a$(B) $b*b=b$Choose the most appropriate answer from the opt…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 8
For the graph; the following sequences of depth first search $(DFS)$ are given(A) $abcghf$(B) $abfchg$(C) $abfhgc$(D) $…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 9
Let $\epsilon=0.0005$ and Let $R_e$ be the relation $\{(x,y)\in R^2:|x-y|<\epsilon\}$, $R_e$ could be interpreted as…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
 10
Match List I with List II:List-IList-IIA. BCNFI. It removes multivalued dependency.B. 3NFII. It is not always dependenc…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
Ask Your Question or Put Your Review.

loading...