Recent questions tagged goclasses-toc-practice-questions

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 the following TM strategy for $L=\{b^ic^i\mid i\ge0\}.$It repeatedly:changes the leftmost unmatched $b$ to $\sqcup$ (blank symbol)$,$ scans right to the end of t...

Consider $L=\{0^n1^n2^n\mid n\ge0\}.$Which of the following gives a correct high-level strategy for a single-tape Turing machine recognizing $L$?Repeatedly mark the leftm...

Suppose a Turing machine makes the following one-step move:$$011q_7\,00101 \;\vdash\; 0110q_7\,0101.$$What transition must have been used, and what is the next configurat...

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...

Let \(I \subseteq \Sigma^*\) be any nonregular language.For every string \(w \notin I\), define $R_w = \Sigma^* - \{w\}.$Now consider $K = \bigcap_{w \notin I} R_w.$What ...

For every $n\geq 0$, define $L_n=\{a^nb^n\}$.Which statement is correct?Every $L_n$ is nonregular, but $\bigcup_{n=0}^{\infty}L_n$ is regular. Every $L_n$ is regular, and...

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=\{...

Let $L$ be a context-free language that is not regular.Which of the following must be true?$L$ is recursive. $L$ is not recursive. There exists a regular grammar $G$ such...

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 $...

Suppose $L_1$ and $L_2$ are both nonregular languages.Which statement about $L_1\cup L_2$ is correct?It must be nonregular. It must be regular. It may be regular or nonre...

Let $L$ be a nonregular language.What can always be concluded about $L^R$?$L^R$ is regular. $L^R$ is nonregular. $L^R$ may be regular or nonregular. Nothing can be conclu...

Suppose $L$ is a deterministic context-free language.Which of the following is always correct about$$L^R=\{w^R\mid w\in L\}?$$$L^R$ must be regular. $L^R$ must be determi...

Consider $$L= \{a^ib^jc^k\mid i=j\text{ or }j=k\}.$$ Which of the following correctly classifies $L$?$L$ is regular. $L$ is DCFL but not regular. $L$ is CFL but not DCFL....

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...

Let $L$ be a context-free language and $R$ be a regular language.Consider the problem$$L-R=\varnothing?$$Which statement is correct?It is decidable because $L-R$ is conte...

For a language $L$, define$$L^R=\{w^R\mid w\in L\}.$$ If $L$ is context-free, which statement is correct?$L^R$ is always regular. $L^R$ is always context-free. $L^R$ may ...

Suppose a language $L$ is accepted by some pushdown automaton.What can always be concluded about $L^*$?$L^*$ must be regular. $L^*$ must be context-free. $L^*$ need not b...

Let $R$ be a regular language and $C$ be a context-free language over the same alphabet.Which statement about $R\cup C$ is always true?$R\cup C$ must be regular. $R\cup C...

The class of context-free languages satisfies which one of the following?It is closed under intersection. It is closed under complementation. It is closed under concatena...

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...