search
Log In

Recent questions tagged theory-of-computation

1 vote
2 answers
1
Consider $L=L_1 \cap L_2$ where $L_1 = \{ 0^m 1^m 20^n 1^n \mid m,n \geq 0 \}$ $L_2 = \{0^m1^n2^k \mid m,n,k \geq 0 \}$ Then, the language $L$ is Recursively enumerable but not context free Regular Context free but not regular Not recursive
asked Nov 20, 2020 in Theory of Computation jothee 171 views
0 votes
2 answers
2
Let $L_1$ and $L_2$ be languages over $\Sigma = \{a,b\}$ represented by the regular expressions $(a^* +b)^*$ and $(a+b)^*$ respectively. Which of the following is true with respect to the two languages? $L_1 \subset L_2$ $L_2 \subset L_1$ $L_1 = L_2$ $L_1 \cap L_2 = \phi$
asked Nov 20, 2020 in Theory of Computation jothee 148 views
1 vote
2 answers
3
Which of the following statements is true? The union of two context free languages is context free The intersection of two context free languages is context free The complement of a context free language is context free If a language is context free, it can always be accepted by a deterministic pushdown automaton
asked Nov 20, 2020 in Theory of Computation jothee 96 views
1 vote
1 answer
4
Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems: Is $L(G_1)=L(G_2)$? Is $L(G_2) \leq L(G_1)$? Is $L(G_1)=R$? Which of the problems are undecidable? Choose the correct answer from the options given below: $(a)$ only $(b)$ only $(a)$ and $(b)$ only $(a)$, $(b)$ and $(c)$
asked Nov 20, 2020 in Theory of Computation jothee 84 views
0 votes
2 answers
5
Consider the following languages: $L_1=\{a^{\grave{z}^z} \mid \grave{Z} \text{ is an integer} \}$ $L_2=\{a^{z\grave{z}} \mid \grave{Z} \geq 0\}$ $L_3=\{ \omega \omega \mid \omega \epsilon \{a,b\}^*\}$ Which of the languages is(are) regular? Choose the correct answer from the options given below: $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_1$ only $L_2$ only
asked Nov 20, 2020 in Theory of Computation jothee 83 views
0 votes
2 answers
6
Which of the following grammars is(are) ambiguous? $s \rightarrow ss \mid asb \mid bsa \mid \lambda$ $s \rightarrow asbs \mid bsas \mid \lambda$ $s \rightarrow aAB \\ A \rightarrow bBb \\ B \rightarrow A \mid \lambda \text{ where } \lambda \text{ denotes empty string}$ Choose the correct answer from the options given below: $(a)$ and $(c)$ only $(b)$ only $(b)$ and $(c)$ only $(a)$ and $(b)$ only
asked Nov 20, 2020 in Theory of Computation jothee 92 views
0 votes
1 answer
7
Match $\text{List I}$ with $\text{List II}$ $L_R:$ Regular language, $LCF$: Context free language $L_{REC}:$ Recursive langauge, $L_{RE}$ ... options given below: $A-II, B-III, C-I$ $A-III, B-I, C-II$ $A-I, B-II, C-III$ $A-II, B-I, C-III$
asked Nov 20, 2020 in Theory of Computation jothee 46 views
0 votes
1 answer
8
Consider the following regular expressions: $r=a(b+a)^*$ $s=a(a+b)^*$ $t=aa^*b$ Choose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above: $L(r) \subseteq L(s) \subseteq L(t)$ $L(r) \supseteq L(s) \supseteq L(t)$ $L(r) \supseteq L(t) \supseteq L(s)$ $L(s) \supseteq L(t) \supseteq L(r)$
asked Nov 20, 2020 in Theory of Computation jothee 68 views
0 votes
1 answer
9
Given below are two statements: Statement $I$: The problem Is $L_1 \wedge L_2 = \phi$? is undecidable for context sensitive languages $L_1$ and $L_2$ Statement $II$: The problem Is $W \in L$? is decidable for context sensitive language $L$. (where $W$ is ... $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
asked Nov 20, 2020 in Theory of Computation jothee 50 views
0 votes
1 answer
10
0 votes
1 answer
11
0 votes
1 answer
12
0 votes
2 answers
13
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens
asked Apr 2, 2020 in Theory of Computation Lakshman Patel RJIT 178 views
1 vote
2 answers
14
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, 2020 in Theory of Computation Lakshman Patel RJIT 230 views
0 votes
1 answer
15
0 votes
1 answer
17
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)$ $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
asked Apr 1, 2020 in Theory of Computation Lakshman Patel RJIT 137 views
0 votes
1 answer
18
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, 2020 in Theory of Computation Lakshman Patel RJIT 169 views
1 vote
4 answers
19
0 votes
3 answers
20
0 votes
2 answers
22
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, 2020 in Theory of Computation Lakshman Patel RJIT 273 views
0 votes
1 answer
24
Let $P, Q, R$ be a regular expression over $\Sigma$. If $P$ does not contain null string, then $R=Q+RP$ has a unique solution ___________ . $Q^{*}P$ $QP^{*}$ $Q^{*}P^{*}$ $\left ( P^{*}O^{*} \right)^{*}$
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 316 views
1 vote
2 answers
26
$\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, 2020 in Theory of Computation Lakshman Patel RJIT 261 views
...