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

Consider the properties of recursively enumerable sets:

(A) Finiteness
(B) Context Freedom
(C) Emptiness
Which of the following is true?

Solution

For recursively enumerable sets, these properties are related to languages accepted by Turing machines.

Now check each property one by one.

(A) Finiteness:

To decide whether a recursively enumerable language is finite or infinite, we need to know all strings accepted by the Turing machine.

But a Turing machine may not halt on some inputs.

So, finiteness of recursively enumerable sets is not decidable.

(B) Context Freedom:

To decide whether a recursively enumerable language is context-free or not is also not decidable.

This is a non-trivial property of the language accepted by a Turing machine.

By Rice's theorem, every non-trivial property of recursively enumerable languages is undecidable.

So, context freedom is not decidable.

(C) Emptiness:

Emptiness means checking whether the language accepted by a Turing machine is empty or not.

That is, we need to decide whether the Turing machine accepts at least one string.

This is also undecidable for recursively enumerable languages.

Therefore, all three properties are not decidable.

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

Nearest first
1
Consider two lists A and B of three strings on $\{0,1\}$X:List AList B11111011110100Y:List AList B1010101111101011Which…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
2
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)
3
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)
4
A trigger is
Topic: UGC NET Computer Science Sep 2022 (Paper II)
5
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)
6
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)
7
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)
8
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)
9
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)
10
Which of the following algorithm design approach is used in Quick sort algorithm?
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 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)
2
 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)
3
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)
4
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)
5
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)
6
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)
7
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)
8
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)
9
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)
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...