# Recent questions tagged theory-of-computation

1
Which of the following are not regular? Strings of even number of a’s Strings of a’s , whose length is a prime number. Set of all palindromes made up of a’s and b’s. Strings of a’s whose length is a perfect square. (a) and (b) only (a), (b) and (c) only (b),(c) and (d) only (b) and (d) only
1 vote
2
Consider the languages $L_{1}= \phi$ and $L_{2}=\{1\}$. Which one of the following represents $L_{1}^{\ast}\cup L_{2}^{\ast} L_{1}^{\ast}$? $\{\in \}$ $\{\in,1\}$ $\phi$ $1^{\ast}$
3
Given the following statements: A class of languages that is closed under union and complementation has to be closed under intersection A class of languages that is closed under union and intersection has to be closed under complementation Which of the following options is correct? Both (a) and (b) are false Both (a) and (b) are true (a) is true, (b) is false (a) is false, (b) is true
4
Let $G= (V,T,S,P)$ be a context-free grammer such that every one of its productions is of the form $A\rightarrow v$, with $\mid v \mid=K> 1$. The derivation tree for any $W \in L(G)$ has a height $h$ ... $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid - 1}{K-1} \right)$
5
Given the following two languages : $L_{1}= \{a^{n}b^{n}, \mid n\geq 0,n \neq 100 \}$ $L_{2}= \{w \in \{a,b,c \} ^{\ast} \mid n_{a}(w)=n_{b}(w)=n_{c}(w) \}$ Which of the following options is correct? Both $L_{1}$ and $L_{2}$ ... are context free language $L_{1}$ is context free language, $L_{2}$ is not context free language $L_{1}$ is not context free language, $L_{2}$ is context free language
6
Which of the following pairs have different expressive power? Single-tape-turing machine and multi-dimensional turing machine. Multi-tape turing machine and multi-dimensional turing machine. Deterministic push down automata and non-deterministic pushdown automata. Deterministic finite automata and Non-deterministic finite automata
7
Which of the following statements is false? Every context –sensitive language is recursive The set of all languages that are not recursively enumerable is countable The family of recursively enumerable languages is closed under union The families of recursively enumerable and recursive languages are closed under reversal
8
Which of the following strings would match the regular expression : $p+ [3-5] * [xyz]$? $p443y$ $p6y$ $3xyz$ $p35z$ $p353535x$ $ppp5$ I, IlI and VI only IV, V and VI only II, IV and V only I, IV and V only
9
Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s? $((0+1)^*1(0+1)^*1)^*10^*$ $(0^*10^*10^*)^*0^*1$ $10^*(0^*10^*10^*)^*$ $(0^*10^*10^*)^*10^*$
10
Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Both Ⅰ and Ⅱ Neither Ⅰ nor Ⅱ
11
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
12
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
13
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ Which one of the following is TRUE? $L_1$ ... $L_1$ context- free but not regular and $L_2$ is context-free. Neither $L_1$ nor $L_2$ is context- free. $L_1$ context- free but $L_2$ is not context-free.
14
Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________
1 vote
15
Consider the following statements. The intersection of two context-free languages is always context-free The super-set of a context-free languages is never regular The subset of a decidable language is always decidable Let $\Sigma = \{a,b,c\}.$ Let $L\subseteq \Sigma$ be the language of all strings in which either ... $(2)$ Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
16
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
1 vote
17
Which of the following classes of languages can validate an $\text{IPv4}$ address in dotted decimal format? It is to be ensured that the decimal values lie between $0$ and $255$. RE and higher CFG and higher CSG and higher Recursively enumerable language
1 vote
18
The language which is generated by the grammar $S \rightarrow aSa \mid bSb \mid a \mid b$ over the alphabet of $\{a,b\}$ is the set of Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes
19
Which of the following is true? Every subset of a regular set is regular Every finite subset of non-regular set is regular The union of two non regular set is not regular Infinite union of finite set is regular
1 vote
20
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
21
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
1 vote
22
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG}$is undecidable.
23
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input$w$} \}$ Is $X$ decidable? Prove your answer.
24
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
25
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
26
Let $f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$ for any natural number $x$. If you start with an integer $x$ and iterate $f$, you obtain a sequence, $x, f(x), f(f(x)), \dots$ ... problem. Suppose that $ATM$ were decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.
1 vote
27
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language consisting of Turing ... any $TMs$. Prove that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$. The squares along the boundary of the rectangle contain the symbol $\#$ and the internal squares contain ... . Consider the problem of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.