Recent questions tagged goclasses-cs-dpp

Which of the following languages are recognizable?$\{\langle M\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ L(M)\ \mathrm{is\ finite}\}$ $\{\langle M_1,M_2,w\rangle\mid M_1\ \m...

Define, $A_{\mathrm{TM}}=\{\langle M,w\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ w\in L(M)\}$.Consider the TM $N$:On input $\langle M,w\rangle$:Simulate $M$ on $w$. If $M$ a...

Which of these statements are true for all choices of TM $M$, string $w$, and language $L$?If $M$ decides $L$ and $M$ rejects $w$, then $w\notin L$. If $M$ decides $L$ an...

Which of these statements are true for all choices of TM $M$, string $w$, and language $L$?If $M$ recognizes $L$ and $M$ rejects $w$, then $w\notin L$. If $M$ recognizes ...

Which of the following languages are Turing-recognizable?$\{\langle M\rangle\mid M\ \mathrm{is\ a\ deterministic\ TM\ and}\ M\ \mathrm{accepts}\ 010\}$ $\{\langle M\rangl...

Let $\mathrm{R}$ and $\mathrm{S}$ be relations.For which of the following relational operations is it not necessary that $\mathrm{R}$ and $\mathrm{S}$ be union-compatible...

The database contains:$\mathrm{Users}(\mathrm{uid},\mathrm{name},\mathrm{dob},\mathrm{user\_type})$$\mathrm{Posts}(\mathrm{pid},\mathrm{folder},\mathrm{summary})$$\mathrm...

The Adjacency List table stores the data for the tree structure shown below. Which SQL keyword should be inserted at $\mathbf{[a]}$ to retrieve the leaf nodes of the tree...

Consider:SQL Statement $\mathbf{1}$$\mathrm{SELECT\ *}$ $\mathrm{FROM\ R}$ $\mathrm{UNION}$ $\mathrm{SELECT\ *}$ $\mathrm{FROM\ R}$;SQL Statement $\mathbf{2}$$\mathrm{SEL...

Consider the following $\mathrm{Product}$ table:$$\begin{array}{|c|c|c|c|} \hline \mathrm{ProductID} & \mathrm{Product} & \mathrm{SupplierID} & \mathrm{UnitPrice} \\ \hli...

Given:$\mathrm{Homes}(\mathrm{home\_id},\mathrm{city},\mathrm{bedrooms},\mathrm{bathrooms},\mathrm{area})$$\mathrm{Transactions}(\mathrm{home\_id},\mathrm{buyer\_id},\mat...

Given the relation: $$\begin{array}{|c|c|c|c|} \hline \mathrm{Sname} & \mathrm{Sid} & \mathrm{Region} & \mathrm{Quota} \\ \hline \mathrm{Frances} & 25 & \mathrm{TX} & 100...

An auditing company was hired to analyze the database of the SUS (Unified Health System). Its first task is to identify pairs of registered doctors who have the same name...

Two tables are given below : $$\begin{array}{c@{\qquad}c}\mathrm{\mathbf{Orders}} & \mathrm{\mathbf{Products}} \\[4pt]\begin{array}{|c|c|c|}\hline\mathrm{Date} & \mathrm{...

A table $\mathrm{Scores}$ stores each student's marks in Japanese and Mathematics.Let,$A$ mean the student's Japanese score is at least the Japanese average.$B$ mean the ...

Which statement is captured by the Church-Turing thesis?Every yes/no decision problem is decidable. The thesis specifically states that some decision problems are neither...

Given an NFA $N$, we want to decide efficiently whether $$L(N)\cap 0^*=\varnothing$$ Which method is appropriate?Convert $N$ to a DFA, take a product with a DFA for $0^*$...

Let, $A_{\mathrm{DFA}}=\{\langle D,w\rangle\mid D\ \mathrm{accepts}\ w\}$,$E_{\mathrm{DFA}}=\{\langle D\rangle\mid L(D)=\varnothing\}$,and$EQ_{\mathrm{DFA}}=\{\langle D_1...

Consider the language corresponding to the problem of recognizing binary palindromes: $$L=\{w\in\{0,1\}^*\mid w=w^R\}$$ Which statement is correct?$L$ is regular and deci...

Consider algorithms for the following tasks:Recognizing palindromes Reversing a string Recognizing Pythagorean triples Computing $\mathrm{gcd}$ of two positive integers T...

Consider the following statements about recursively enumerable languages:The family of recursively enumerable languages is closed under union. Given input $w$, one may no...

Consider the following statements:If a DFA can decide membership in a language $L$, then some Turing machine can also decide membership in $L$. If a Turing machine can de...

Is the intersection of an arbitrary Turing-recognizable language and an arbitrary co-Turing-recognizable language necessarily decidable?Yes, because of the containment di...

Suppose a language $L$ is undecidable but Turing-recognizable. What must be true?This situation is impossible. $\overline{L}$ must be decidable. $\overline{L}$ must be Tu...

Which of the following correctly describes the relationship between decidable and Turing-recognizable languages?Decidable languages are a subset of Turing-recognizable la...

Consider the relation $\mathrm{Sailors}(\mathrm{sid},\mathrm{sname},\mathrm{rating},\mathrm{age})$ and the following TRC expression: $$\{S\mid \neg(S\in \mathrm{Sailors})...

Consider $\mathrm{Student}(\mathrm{sid},\mathrm{name},\mathrm{univ}),\mathrm{Enrollment}(\mathrm{sid},\mathrm{cid}).$Using the above schema, which condition correctly cha...

Consider$\mathrm{Course}(\mathrm{cid},\mathrm{name},\mathrm{year},\mathrm{duration})$$\mathrm{Student}(\mathrm{sid},\mathrm{name},\mathrm{univ})$$\mathrm{Instructor}(\mat...

Using the same $\mathrm{Manager}$, $\mathrm{Stores}$, $\mathrm{Sales}$, and $\mathrm{Products}$ schema from the exam, define:$\mathrm{NailSale}(S)$ = store $S$ sold more ...

Consider $\mathrm{Manager}(\mathrm{NAME})$ and $\mathrm{Stores}(\mathrm{STORE\_ID},\mathrm{ADDRESS},\mathrm{REGION},\mathrm{MANAGER})$.Which TRC expression correctly retu...