search
Log In

Recent questions and answers in Theory of Computation

44 votes
6 answers
1
Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed DFA that accepts this ...
answered 6 days ago in Theory of Computation vipin.gautam1906 5.6k views
22 votes
7 answers
2
Consider the languages: $L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$ and $ L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$ Which one of the following statements is FALSE? $L_1 \cap L_2$ is a context-free language $L_1 \cup L_2$ is a context-free language $L_1 \text{ and } L_2$ are context-free languages $L_1 \cap L_2$ is a context sensitive language
answered Oct 19 in Theory of Computation Shashank Rustagi 3.7k views
31 votes
5 answers
3
Consider the machine $M$: The language recognized by $M$ is: $\left\{ w \in \{a, b\}^* \text{ | every a in $w$ is followed by exactly two $b$'s} \right\}$ $\left\{w \in \{a, b\}^* \text{ | every a in $w$ is followed by at least two $b$'s} \right\}$ ... $ contains the substring $abb$'} \right\}$ $\left\{w \in \{a, b\}^* \text{ | $w$ does not contain $aa$' as a substring} \right\}$
answered Oct 15 in Theory of Computation shubhamladey 4.3k views
54 votes
3 answers
6
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false
answered Oct 13 in Theory of Computation Musa 10.3k views
0 votes
1 answer
7
1 vote
1 answer
8
Find a grammar equivalent to $S\rightarrow aAB, A\rightarrow bBb, B\rightarrow A|\lambda$ that satisfies the conditions of Theorem 5.2. Theorem 5.2 Suppose that $G = (V, T, S, P)$ is a context-free grammar that does not have any rules of the form $A → λ,$ ... can be made into an algorithm which, for any $w ∈ Σ^*,$ either produces a parsing of $w$ or tells us that no parsing is possible.
answered Oct 12 in Theory of Computation JAINchiNMay 123 views
27 votes
3 answers
10
Which of the following is TRUE? Every subset of a regular set is regular Every finite subset of a non-regular set is regular The union of two non-regular sets is not regular Infinite union of finite sets is regular
answered Oct 12 in Theory of Computation Musa 5.8k views
1 vote
1 answer
14
0 votes
1 answer
20
Define what one might mean by properly nested parenthesis structures involving two kinds of parentheses, say ( ) and [ ]. Intuitively, properly nested strings in this situation are ([ ]), ([[ ]])[( )], but not ([ )] or (( ]]. Using your definition, give a context-free grammar for generating all properly nested parentheses.
answered Oct 11 in Theory of Computation JAINchiNMay 16 views
0 votes
1 answer
21
0 votes
1 answer
28
0 votes
4 answers
31
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0, k ≥ 0$). (a) $L =$ {$a^nb^mc^k : n = m$ or $m ≤ k$}. (b) $L =$ {$a^nb^mc^k : n = m$ or $m ≠ k$}. (c) $L =$ {$a^nb^mc^k : k = n + m$}. (d) $L =$ {$a^nb^mc^k : n + 2m = k$}. (e) $L =$ ... $a, b, c$}$^* : n_a (w) + n_b (w) ≠ n_c (w)$}. (g) $L =$ {$a^nb^mc^k, k ≠ n + m$}. (h) $L =$ {$a^nb^mc^k : k ≥ 3$}.
answered Oct 11 in Theory of Computation JAINchiNMay 86 views
1 vote
5 answers
32
Find context free grammars for the following languages (with n>=0, m>=0, k>=0) (a) L={anbmck : n=m or m<=k} (b) L={ anbmck : n=m or m≠k} (c) L={anbmck : k=n+m } (d) L={ anbmck : n+2m=k} (e) L={anbmck : k=|n-m| } (f) L={ w ∈ {a,b,c}* : na(w)+nb(w)≠nc(w) } (g) L={ anbmck : k≠n+m } (h) L= { anbmck : K>=3}
answered Oct 10 in Theory of Computation JAINchiNMay 1.5k views
0 votes
6 answers
33
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0$). (a) $L =$ {$a^nb^m : n ≤ m + 3$}. (b) $L =$ {$a^nb^m : n ≠ m − 1$}. (c) https://gateoverflow.in/208410/peter-linz-edition-4-exercise-5-1-question-7-c-page-no-133 (d) $L =$ {$a^nb^m : 2n ≤ m ≤ 3n$ ... $^* : n_a (v) ≥ n_b (v),$ where $v$ is any prefix of $w$}. (g) $L =$ {$w ∈$ {$a,b$}$^* : n_a (w) = 2n_b(w) + 1$}.
answered Oct 10 in Theory of Computation JAINchiNMay 174 views
3 votes
2 answers
34
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 in Theory of Computation Sanjay Sharma 427 views
0 votes
1 answer
35
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
36
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
38
1 vote
2 answers
39
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
To see more, click for all the questions in this category.
...