Recent questions tagged goclasses-toc-practice-questions

The following grammar is in Greibach Normal Form and generates balanced brackets:$S\rightarrow [B$$B\rightarrow ]\mid ~]S\mid [BB$.Consider a derivation of $[[][]][]$.Whi...

Consider the following statements about grammars and languages.A grammar in Chomsky Normal Form can be ambiguous. An ambiguous grammar can generate a language that also h...

Which one of the following grammars is in Chomsky Normal Form?Terminals are lowercase and nonterminals are uppercase.$X\rightarrow YZ$$Y\rightarrow a$$Z\rightarrow bc$ $X...

Suppose two different variables in a context-free grammar $G$ can each derive $\epsilon$.Which statement must necessarily follow?$G$ is ambiguous. $\epsilon\in L(G)$. Con...

Consider the CFG $$\begin{aligned}S &\rightarrow X \mid 00 \mid \epsilon \\X &\rightarrow 0 \mid \epsilon\end{aligned}$$After removing the unit production, which grammar ...

Consider the NFA shown below, where $A$ is the initial state and $D$ is the only accepting state.Which DFA accepts the same language?Initial state: $A$Accepting states: $...

Which of the following is true?There is no known algorithm for checking whether a regular language is nonempty. The proof of the pumping lemma was a proof by induction. T...

Which of the following statements about regular languages are true?For every language generated by a regular grammar, there exists a finite automaton, DFA or NFA, that ac...

Let an NFA have $\mathbf{6}$ states.After applying the standard NFA-to-DFA conversion algorithm, what is the maximum possible number of states in the resulting DFA, inclu...

Consider the following regular expressions over the alphabet$\Sigma=\{a,b\}$.$R_1=a(a\cup b)^*$$R_2=b(a\cup b)^*$If $L(R)$ denotes the language associated with regular ex...

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

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

Let $M$ be a deterministic Turing machine. During a computation on input $w$, suppose $M$ enters exactly the same complete configuration at two different times before rea...

A deterministic Turing machine starts on a blank tape.Which of the following gives an example of a computation that runs forever without ever repeating exactly the same c...

Suppose $M$ recognizes a Turing-recognizable language $A$.Which statement is necessarily true?There must exist some $w\notin A$ on which $M$ loops forever. $M$ must loop ...

Let $L$ be any Turing-recognizable language.Which of the following is always possible?Construct a TM that accepts every $w\in L$ and loops forever on every $w\notin L$, n...

Consider the following deterministic Turing machine $M$ with input alphabet $\Sigma=\{a,b\}$What is $L(M)$?$\{w\in\{a,b\}^*\mid w\text{ ends in }a\}$ $\{w\in\{a,b\}^*\mid...