Recent questions tagged multiple-selects

Let $M$ be a Turing machine that recognizes language $L$, and suppose $w\notin L.$Which of the following behaviors are possible when $M$ is run on $w$?$M$ accepts $w$. $M...

Consider a deterministic single-tape Turing machine$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\text{accept}},q_{\text{reject}}).$$Which of the following are required in the stand...

Consider $\mathrm{Flights}(\mathrm{num},\mathrm{src},\mathrm{dst})$, where each tuple represents a directed flight from $\mathrm{src}$ to $\mathrm{dst}$.Let $\mathrm{F}_1...

Consider $\mathrm{Homes}(\mathrm{home\_id},\mathrm{city},\ldots)$ and $\mathrm{Transactions}(\mathrm{home\_id},\mathrm{sale\_price},\ldots)$.We want every home in Berkele...

Let $\Sigma=\{0,1\}.$Which of the following are valid examples?$A=\{01\}, \qquad B=\{0^n1^n\mid n\ge0\}$where $A$ is regular, $B$ is nonregular, and $A\subseteq B$. $C=\{...

Consider the grammar $$S\rightarrow aS\mid Sb\mid b$$ Which of the following statements are correct?The given grammar is a Type $3$ grammar. The given grammar is a Type $...

Let $L_1,L_2$ be deterministic context-free languages and let $R$ be a regular language.Which of the following statements are always true?$L_1\cup L_2$ is deterministic c...

Assume the expressions below are schema-valid and relations use set semantics.Which of the following are always true?$(\mathrm{R}\bowtie\mathrm{S})\bowtie\mathrm{T}=(\mat...

Consider the relations:$\mathrm{Users(username, name, email, password, address)}$and$\mathrm{FriendsWith(username, username2, sincewhen)}$.A friendship tuple indicates th...

Consider $\text{parts(pno, pname, price)}$.Which relational algebra expression returns exactly the names of all parts whose price is greater than $\$200$?$\pi_{\text{pnam...

For languages $X,Y\subseteq\Sigma^*$, define$$X/Y = \{w:\exists y\in Y,\ wy\in X\}$$ Suppose $X$ is regular, but nothing is assumed about $Y$.Which statement is always tr...

Let $X$ and $Y$ be regular languages. Their symmetric difference is$$X\triangle Y=\{w:w\text{ belongs to exactly one of }X,Y\}$$. Which expression correctly represents $X...

Let $M$ and $N$ be two DFAs. Define$$Z=\{u_1v_1u_2v_2\cdots u_kv_k : k\ge0, ~u_i\in L(M), ~v_i\in L(N)\}.$$Which regular-language expression describes $Z$?$L(M)^*L(N)^*$ ...

Let $L$ be an arbitrary regular language over $\Sigma$, and define$$K=\{w\in\Sigma^*:w^Rw\in L\}$$.Which statement is correct?$K$ is always regular. $K$ is regular only i...

For an arbitrary language $L$, which of the following statements is correct?If $L^*$ is regular, then $L$ must be regular. If $L$ is nonregular, then $L^*$ must be nonreg...

Let $L_1$ and $L_2$ be regular languages and let $L_3$ be non-regular. Which statements are always true?$L_1=L_2$ iff $L_1\cap\overline{L_2}=\emptyset$ $L_1\cup L_3$ is n...

Consider,Statement $1:$ If a language family is closed under union and complement, then it must also be closed under intersection. Statement $2:$ An NFA can be constructe...

Which statements are true?Every language recognized by an $n$-state DFA can be recognized by an NFA with $n$ states. Every language recognized by an $n$-state NFA can be ...

Let $L_1$ be regular where specified. Which of the following languages are guaranteed to be regular?$\{ww\mid w\in{0,1}^*\}$ $\{ww\mid w\in L_1\}$ $\{w\mid ww\in L_1\}$ $...

All languages are over $\{0,1\}$. Which statements are true?If $L_1\subseteq L_2$ and $L_2$ is regular, then $L_1$ must be regular. If $L_1$ and $L_2$ are both non-regula...

Consider $R(A,B,C,D,E,F,G)$ with $F=\{AB\to CF,\ CD\to EA,\ E\to ABC,\ B\to F,\ C\to D\}$.Suppose $R$ is decomposed into $R_1(A,B,C,D,E,G)$ and $R_2(B,F)$.Which statement...

Consider $R(A,B,C,D,E,F,G)$ with $F=\{BCD\to A,\ BC\to E,\ A\to F,\ F\to G,\ C\to D,\ A\to G\}$.Which of the following statements are correct after applying the $\text{3N...

Let $P=\{a^n\mid n\text{ is prime}\}$.Which statements are correct?$P$ is regular. $P$ is CFL but not regular. If $P$ were CFL, then because it is unary, it would have to...

Let $\text{COPY}=\{ww\mid w\in\{a,b\}^*\}$ and $\text{NOTCOPY}=\{x\in\{a,b\}^*\mid x\text{ is not of the form }ww\}$.Which statements are correct?$\text{COPY}$ is not CFL...

Let $B=\{0^n\#0^{2n}\#0^{3n}\mid n\ge0\}$.Which statements are correct for proving $B$ is not CFL using the pumping lemma?Choose $s=0^p\#0^{2p}\#0^{3p}$, where $p$ is the...

Let $A=\{w\in\{a,b,c\}^*\mid \#a(w)=\#b(w)=\#c(w)\}$ and let $R=a^*b^*c^*$. Which statements are correct?$R$ is regular. If $A$ were CFL, then $A\cap R$ would be CFL. $A\...

Consider the following languages:$L_1=\{w\in\{a,b\}^*\mid \#a(w)=\#b(w)\}$$L_2=\{w\in\{a,b,c\}^*\mid \#a(w)=\#b(w)=\#c(w)\}$$L_3=\{a^m b^n\mid 5m+4n=44,\ m,n\ge0\}$Which ...

Let $L=\{w\in\{a,b\}^*\mid n_a(w)\ne n_b(w)\}$. Which statements are correct?$L$ is regular. $L$ is DCFL. $L$ is not CFL. A DPDA can maintain the current surplus using th...

Let $L_1=\{wcw^R\mid w\in\{a,b\}^*\}$ and $L_2=\{ww^R\mid w\in\{a,b\}^*\}$. Which statements are correct?$L_1$ is a DCFL. $L_2$ is a DCFL. $L_2$ is a CFL. $L_2$ is not ac...