search
Log In

Recent questions and answers in Theory of Computation

2 votes
2 answers
1
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$, represents $(q,Y) \in \delta(p,a,X). $ Consider the ... $\Gamma = \{ \#, A\}$. The number of strings of length $100$ accepted by the above pushdown automaton is ___________
answered 6 days ago in Theory of Computation Kanwae Kan 557 views
2 votes
3 answers
2
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is ... $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$
answered Apr 1 in Theory of Computation Nikhil_dhama 529 views
3 votes
2 answers
3
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free? $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
answered Mar 25 in Theory of Computation Deepakk Poonia (Dee) 554 views
3 votes
3 answers
4
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal $\text{DFA}$ with $k$ states. Which one of the following languages must necessarily be accepted by a minimal $\text{DFA}$ with $k$ states? $L-\{01\}$ $L \cup \{01\}$ $\{0,1\}^* – L$ $L \cdot L$
answered Mar 25 in Theory of Computation Deepakk Poonia (Dee) 657 views
0 votes
1 answer
6
Give an algorithm that takes a DFA $A$ and computes the number of strings of length $n$ $($for some given $n$ not related to the number of states of $A)$ accepted by $A.$Your algorithm should be polynomial in both $n$ and the number of states of $A.$
answered Mar 10 in Theory of Computation Abuzar Mahmoood 93 views
2 votes
3 answers
7
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$ ... and $L_2$ are decidable $L_1$ is decidable and $L_2$ is undecidable $L_1$ is undecidable and $L_2$ is decidable Both $L_1$ and $L_2$ are undecidable
answered Feb 28 in Theory of Computation Vallabh Mandare 451 views
1 vote
3 answers
8
Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free? $L_1 \cap \overline{L_2} \\$ $\overline{\overline{L_1} \cup \overline{L_2}} \\$ $L_1 \cup (L_2 \cup \overline{L_2}) \\$ $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
answered Feb 23 in Theory of Computation Kanwae Kan 603 views
1 vote
3 answers
9
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free? $L_1 \cap L_2$ $L_1 \cdot L_2$ $L_1- L_2$ $L_1\cup L_2$
answered Feb 19 in Theory of Computation Ashwani Kumar 2 483 views
0 votes
1 answer
10
Consider the following language: $L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$ Which one of the following deterministic finite automata accepts $L?$ ​​​​​​​
answered Feb 19 in Theory of Computation Bhargav D Dave 6 288 views
2 votes
1 answer
11
​​​​​​Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true
answered Feb 18 in Theory of Computation Deepakk Poonia (Dee) 539 views
2 votes
1 answer
12
​​​​​​​Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$
answered Feb 18 in Theory of Computation zxy123 471 views
0 votes
1 answer
13
Suppose we want to design a synchronous circuit that processes a string of $0$'s and $1$'s. Given a string, it produces another string by replacing the first $1$ in any subsequence of consecutive $1$'s by a $0$ ... $\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}$
answered Feb 18 in Theory of Computation zxy123 410 views
0 votes
2 answers
15
The context-free languages are closed for : Intersection Union Complementation Kleene Star (i) and (iv) (i) and (iii) (ii) and (iv) (ii) and (iii)
answered Feb 15 in Theory of Computation Hira Thakur 126 views
32 votes
5 answers
16
What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states? $L$ must be $\{a^n \mid n \ \text{ is odd}\}$ $L$ must be $\{a^n \mid n \ \text{ is even}\}$ $L$ must be $\{a^n \mid n \geq 0\}$ Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$
answered Feb 14 in Theory of Computation Arjun 4.4k views
4 votes
3 answers
17
Let $P$ be a Mealy machine that has $N$ states and $M$ outputs. Let $Z$ be the number of states of the corresponding Moore machine $Q$ which is equivalent to $P$. Which of the following conditions always holds? $Z<M+N$ $Z=M*N$ $Z=P*M+Q*N$ $Z \leq M*N$
answered Feb 12 in Theory of Computation Sourav Ganguly 910 views
22 votes
5 answers
18
If $L$ is a regular language over $\Sigma = \{a,b\} $, which one of the following languages is NOT regular? $L.L^R = \{xy \mid x \in L , y^R \in L\}$ $\{ww^R \mid w \in L \}$ $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* $such that$ \ xy \in L\}$ $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* $such that$ \ xy \in L\}$
answered Feb 3 in Theory of Computation Accel_Blaze 7.5k views
8 votes
3 answers
19
2 votes
3 answers
20
Given that: { A^m B^n C^k/ if (k=even) then m=n} { A^m B^n C^k/ if (n=even) then m=k} Which of the above languages are DCFL? According to me it is CFL as we have to first count k and then compare other inputs.. same for second language but ... given is both are DCFL? it is only possible if skip path is exists here? does it exist for DCFLs? so confused please guide me? if given answer is correct?
answered Feb 1 in Theory of Computation Joey 689 views
16 votes
8 answers
21
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
answered Jan 27 in Theory of Computation ijnuhb 4.5k views
42 votes
2 answers
22
$L_1$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots .$ Define another language $L_2$ over $\Sigma \cup \left\{\text{#}\right\}$ ... $S_1$ is true but $S_2$ is not necessarily true $S_2$ is true but $S_1$ is not necessarily true Neither is necessarily true
answered Jan 24 in Theory of Computation Ramyanee 6.6k views
0 votes
2 answers
23
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
answered Jan 20 in Theory of Computation Joey 178 views
0 votes
2 answers
24
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
answered Jan 20 in Theory of Computation Joey 228 views
1 vote
2 answers
25
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 299 views
0 votes
2 answers
26
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 275 views
1 vote
2 answers
27
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 161 views
1 vote
1 answer
28
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 151 views
0 votes
1 answer
29
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 94 views
0 votes
1 answer
30
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 152 views
0 votes
1 answer
31
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 112 views
3 votes
2 answers
32
Which of the following is not a monotonically increasing grammar? (A) Context-sensitive grammar (B) Unrestricted grammar (C) Regular grammar (D) Context-free grammar
asked Jul 20, 2020 in Theory of Computation Sanjay Sharma 618 views
1 vote
1 answer
33
0 votes
1 answer
34
0 votes
1 answer
35
0 votes
2 answers
36
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 225 views
1 vote
2 answers
37
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 261 views
0 votes
1 answer
38
0 votes
1 answer
40
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 156 views
To see more, click for all the questions in this category.
...