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

Which of the following problems is/are decidable problem(s) on Turing machine $M$?

$(a)$ $G$ is a CFG with $L(G)=\phi$

$(b)$ There exist two TMs $M_1$ and $M_2$ such that $L(M)\subseteq L(M_1)\cup L(M_2)$

$(c)$ $M$ is a TM that accepts $\omega$ using at most $2^{|\omega|}$ cells of tape

Solution

Statement $(a)$ is decidable because emptiness of a context-free grammar is decidable.

Statement $(b)$ is also decidable in this form, because recursively enumerable languages are closed under union, and the condition can be satisfied by suitable Turing machines.

Statement $(c)$ is decidable because the tape usage is bounded by $2^{|\omega|}$. With bounded tape, the number of configurations becomes finite, so we can decide whether $M$ accepts $\omega$ within this bound.

Therefore, all three statements are decidable.

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

Nearest first
1
Consider the following grammar: $S\to XY$ $X\to YaY\mid a$ $Y\to bbX$ Which of the following statements is/are true abo…
Topic: UGC NET Computer Science June 2019 (Paper II)
2
How can the decision algorithm be constructed for deciding whether context-free language $L$ is finite? $(a)$ By constr…
Topic: UGC NET Computer Science June 2019 (Paper II)
3
Match List-I with List-II: List-I List-II (a) $\overlin…
Topic: UGC NET Computer Science June 2019 (Paper II)
4
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression …
Topic: UGC NET Computer Science June 2019 (Paper II)
5
Shift-reduce parser consists of:$(a)$ Input buffer $(b)$ Stack $(c)$ Parse table Choose the correct option from those …
Topic: UGC NET Computer Science June 2019 (Paper II)
6
Replacing the expression $4*2.14$ by $8.56$ is known as:
Topic: UGC NET Computer Science June 2019 (Paper II)
7
On translating the expression given below into quadruple representation, how many operations are required?$(ij)+(e+f)(a…
Topic: UGC NET Computer Science June 2019 (Paper II)
8
Which data structure is used by the compiler for managing variables and their attributes?
Topic: UGC NET Computer Science June 2019 (Paper II)
9
Consider the following statements: $S_1$: For any integer $n>1$, $a^{\phi(n)}\equiv 1\ (\text{mod }n)$ for all $a\in…
Topic: UGC NET Computer Science June 2019 (Paper II)
10
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a real-valued function $f…
Topic: UGC NET Computer Science June 2019 (Paper II)

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

Ascending by ID
1
for a statement, a language $L\subseteq \Sigma^*$ is recursive if there exists some Turing machine $M$. Which of the fo…
Topic: UGC NET Computer Science June 2019 (Paper II)
2
A fully connected network topology is a topology in which there is a direct link between all pairs of nodes. Given a fu…
Topic: UGC NET Computer Science June 2019 (Paper II)
3
What is the name of the protocol that allows a client to send a broadcast message with its MAC address and receive an I…
Topic: UGC NET Computer Science June 2019 (Paper II)
4
You are designing a link layer protocol for a link with a bandwidth of $1$ Gbps over a fiber link with a length of $800…
Topic: UGC NET Computer Science June 2019 (Paper II)
5
You need $500$ subnets, each with about $100$ usable host addresses per subnet. What network mask will you assign using…
Topic: UGC NET Computer Science June 2019 (Paper II)
6
Consider the following two statements with respect to IPv4 in computer networking: $P$: The loopback IP address is a me…
Topic: UGC NET Computer Science June 2019 (Paper II)
7
In the TCP/IP model, encryption and decryption are functions of the _____ layer.
Topic: UGC NET Computer Science June 2019 (Paper II)
8
Which of the following statements is/are true with regard to various layers in the Internet stack?$P$: At the link laye…
Topic: UGC NET Computer Science June 2019 (Paper II)
9
What percentage of the IPv4 address space do all class C addresses consume?
Topic: UGC NET Computer Science June 2019 (Paper II)
10
The ability to inject packets into the Internet with a false source address is known as:
Topic: UGC NET Computer Science June 2019 (Paper II)
Ask Your Question or Put Your Review.

loading...