search
Log In

Recent questions tagged theory-of-computation

0 votes
1 answer
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
asked Mar 24 in Theory of Computation jothee 106 views
1 vote
2 answers
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}$
asked Mar 24 in Theory of Computation jothee 99 views
0 votes
2 answers
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
asked Mar 24 in Theory of Computation jothee 80 views
0 votes
0 answers
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)$
asked Mar 24 in Theory of Computation jothee 80 views
0 votes
2 answers
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
asked Mar 24 in Theory of Computation jothee 99 views
0 votes
2 answers
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
asked Mar 24 in Theory of Computation jothee 74 views
0 votes
1 answer
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
asked Mar 24 in Theory of Computation jothee 38 views
0 votes
2 answers
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
asked Mar 24 in Theory of Computation jothee 159 views
7 votes
5 answers
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^*$
asked Feb 12 in Theory of Computation Arjun 3.1k views
2 votes
4 answers
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 Ⅱ
asked Feb 12 in Theory of Computation Arjun 1.6k views
3 votes
4 answers
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
asked Feb 12 in Theory of Computation Arjun 1.9k views
8 votes
6 answers
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
asked Feb 12 in Theory of Computation Arjun 1.5k views
4 votes
4 answers
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.
asked Feb 12 in Theory of Computation Arjun 2k views
4 votes
4 answers
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 _________
asked Feb 12 in Theory of Computation Arjun 1.4k views
1 vote
2 answers
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.
asked Feb 11 in Theory of Computation Lakshman Patel RJIT 154 views
3 votes
6 answers
16
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
asked Jan 13 in Theory of Computation Satbir 716 views
1 vote
2 answers
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
asked Jan 13 in Theory of Computation Satbir 393 views
1 vote
4 answers
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
asked Jan 13 in Theory of Computation Satbir 238 views
2 votes
2 answers
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
asked Jan 13 in Theory of Computation Satbir 245 views
1 vote
3 answers
20
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
asked Jan 13 in Theory of Computation Satbir 278 views
3 votes
0 answers
21
1 vote
0 answers
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 70 views
0 votes
1 answer
23
0 votes
0 answers
24
0 votes
0 answers
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}\}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 71 views
0 votes
0 answers
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 52 views
1 vote
0 answers
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} \}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 52 views
0 votes
0 answers
28
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
29
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 42 views
0 votes
0 answers
30
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 108 views
...