search
Log In

Recent questions tagged theory-of-computation

0 votes
1 answer
1
If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called decidable undecidable interpretive non-deterministic
asked Apr 2 in Theory of Computation Lakshman Patel RJIT 48 views
0 votes
1 answer
2
The defining language for developing a formalism in which language definitions can be stated, is called syntactic meta language decidable language intermediate language high level language
asked Apr 2 in Theory of Computation Lakshman Patel RJIT 76 views
0 votes
1 answer
4
1 vote
2 answers
5
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ Only $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
asked Apr 1 in Theory of Computation Lakshman Patel RJIT 151 views
0 votes
1 answer
8
0 votes
1 answer
9
Choose the correct statements. A total recursive function is also a partial recursive function A partial recursive function is also a total recursive function A partial recursive function is also a primitive recursive function None of the above
asked Apr 1 in Theory of Computation Lakshman Patel RJIT 81 views
0 votes
3 answers
11
0 votes
2 answers
13
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 111 views
0 votes
1 answer
15
1 vote
1 answer
17
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 129 views
0 votes
2 answers
22
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 172 views
1 vote
3 answers
23
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 153 views
1 vote
3 answers
24
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 128 views
0 votes
0 answers
25
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 138 views
0 votes
3 answers
26
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 210 views
0 votes
3 answers
27
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 126 views
0 votes
1 answer
28
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 56 views
0 votes
2 answers
29
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 244 views
7 votes
5 answers
30
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 4.5k views
...