Aspire Faculty ID #19062 · Topic: UGC NET Computer Science Dec 2019 (Paper II) · Just now
UGC NET Computer Science Dec 2019 (Paper II)

 Let $A={001,0011,11,101}$ and $B={01,111,111,010}$. Similarly, let $C={00,001,1000}$ and $D={0,11,011}$. Which of the following pairs have a post-correspondence solution?

Solution

For pair $(A,B)$:

Take sequence of indices:

$3,4,1$

From $A$ side:

$A_3A_4A_1=11\ 101\ 001=11101001$

From $B$ side:

$B_3B_4B_1=111\ 010\ 01=11101001$

Both strings are equal.

So, pair $(A,B)$ has a PCP solution.

For pair $(C,D)$:

Starting must be with first pair because only it gives matching prefix:

$C_1=00,\ D_1=0$

After this, extra $0$ remains on upper side. Repeating first pair keeps increasing extra zeros, and other pairs do not match the required prefix properly.

So, pair $(C,D)$ has no PCP solution.

Previous 10 Questions — UGC NET Computer Science Dec 2019 (Paper II)

Nearest first
1
Consider the following statements: $S_1:$ There exists no algorithm for deciding if any two Turing machines $M_1$ and $…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
2
 Consider the following language families: $L_1\equiv$ The context-free languages $L_2\equiv$ The context-sensitiv…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
3
Let $G=(V,T,S,P)$ be any context-free grammar without any $\lambda$-productions or unit productions. Let $K$ be the max…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
4
Consider the following languages: $L_1={a^n b^n c^m}\cup{a^n b^m c^m},\ n,m\ge 0$ $L_2={ww^R\mid w\in{a,b}^*}$ where $R…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
5
Consider the following statements with respect to the language $L={a^n b^n\mid n\ge 0}$ $S_1:L^2$ is context free langu…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
6
Consider $\Sigma={w,x}$ and $T={x,y,z}$. Define homomorphism $h$ by: $h(x)=xzy$ $h(w)=zxyy$ If $L$ is the regular langu…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
7
Consider the following grammar: $S\rightarrow 0A\mid 0BB$ $A\rightarrow 00A\mid \lambda$ $B\rightarrow 1B\mid 11C$ $C\r…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
8
Consider the language $L={a^n b^{n-3}\mid n>2}$ on $\Sigma={a,b}$. Which one of the following grammars generates the…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
9
 Consider the following grammars: $G_1:S\rightarrow aSb\mid bSa\mid aa$ $G_2:S\rightarrow aSb\mid bSa\mid SS\mid \…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
10
The time complexity to multiply two polynomials of degree $n$ using Fast Fourier transform method is:
Topic: UGC NET Computer Science Dec 2019 (Paper II)

Next 10 Questions — UGC NET Computer Science Dec 2019 (Paper II)

Ascending by ID
1
Which of the following class of IP address has the last address as $223.255.255.255$?
Topic: UGC NET Computer Science Dec 2019 (Paper II)
2
Consider a subnet with $720$ routers. If a three-level hierarchy is chosen, with eight clusters, each containing $9$ re…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
3
Piconet is a basic unit of a bluetooth system consisting of $...............$ master node and up to $...............$ a…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
4
A network with bandwidth of $10$ Mbps can pass only an average of $12000$ frames per minute with each frame carrying an…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
5
 The full form of ICANN is:
Topic: UGC NET Computer Science Dec 2019 (Paper II)
6
According to Dempster-Shafer theory for uncertainty management, where $Bel(A)$ denotes belief of event $A$.
Topic: UGC NET Computer Science Dec 2019 (Paper II)
7
Consider the following statements: $S_1:\forall xP(x)\vee \forall xQ(x)$ and $\forall x(P(x)\vee Q(x))$ are not logical…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
8
Consider the game tree given below.Here $\circ$ and $\square$ represent MIN and MAX nodes respectively. The value of th…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
9
Consider the following models: $M_1:$ Mamdani model $M_2:$ Takagi-Sugeno-Kang model $M_3:$ Kosko's additive model $($SA…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
10
A fuzzy conjunction operator $t(x,y)$ and a fuzzy disjunction operator $s(x,y)$ form a pair if they satisfy: $t(x,y)=1-…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
Ask Your Question or Put Your Review.

loading...