menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Recent questions and answers in Theory of Computation

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions and answers in Theory of Computation

44 votes
6 answers
1
GATE2012-46
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 ...
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
GATE2005-55
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
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
GATE2005-53
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\}$
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
GATE2016-2-42
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
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
Peter Linz Edition 4 Exercise 5.2 Question 17 (Page No. 145)
Use the exhaustive search parsing method to parse the string $abbbbbb$ with the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A|\lambda.$ In general, how many rounds will be needed to parse any string $w$ in this language?
Use the exhaustive search parsing method to parse the string $abbbbbb$ with the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A|\lambda.$ In general, how many rounds will be needed to parse any string $w$ in this language?
answered Oct 12 in Theory of Computation JAINchiNMay 79 views
1 vote
1 answer
8
Peter Linz Edition 4 Exercise 5.2 Question 20 (Page No. 145)
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 ... algorithm which, for any $w ∈ Σ^*,$ either produces a parsing of $w$ or tells us that no parsing is possible.
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
GATE2007-7
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
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
Theory of computation - Grammer
here answer is given is A won''t it be B? as with A we cannot get 100 string,but with B we can
here answer is given is A won''t it be B? as with A we cannot get 100 string,but with B we can
answered Oct 11 in Theory of Computation JAINchiNMay 158 views
0 votes
1 answer
20
Peter Linz Edition 4 Exercise 5.1 Question 22 (Page No. 135)
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.
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
Peter Linz Edition 4 Exercise 5.1 Question 21 (Page No. 135)
Consider the derivation tree below. Find a grammar $G$ for which this is the derivation tree of the string $aab$. Then find two more sentences of $L(G)$. Find a sentence in $L(G)$ that has a derivation tree of height five or larger.
Consider the derivation tree below. Find a grammar $G$ for which this is the derivation tree of the string $aab$. Then find two more sentences of $L(G)$. Find a sentence in $L(G)$ that has a derivation tree of height five or larger.
answered Oct 11 in Theory of Computation JAINchiNMay 52 views
0 votes
1 answer
28
Peter Linz Edition 4 Exercise 5.1 Question 13 (Page No. 134)
Let $L =$ {$a^nb^n : n ≥ 0$}. (a) https://gateoverflow.in/305106/peter-linz-edition-4-exercise-5-1-question-13-a-page-no-134 (b) Show that $L^k$ is context-free for any given $k ≥ 1$. (c) Show that $\overline{L}$ and $L^*$ are context-free.
Let $L =$ {$a^nb^n : n ≥ 0$}. (a) https://gateoverflow.in/305106/peter-linz-edition-4-exercise-5-1-question-13-a-page-no-134 (b) Show that $L^k$ is context-free for any given $k ≥ 1$. (c) Show that $\overline{L}$ and $L^*$ are context-free.
answered Oct 11 in Theory of Computation JAINchiNMay 42 views
0 votes
4 answers
31
Peter Linz Edition 4 Exercise 5.1 Question 8 (Page No. 134)
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 =$ ... $L =$ {$a^nb^mc^k, k ≠ n + m$}. (h) $L =$ {$a^nb^mc^k : k ≥ 3$}.
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
Peter Linz Exercise 5.1
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}
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
Peter Linz Edition 4 Exercise 5.1 Question 7 (Page No. 133)
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$ ... $v$ is any prefix of $w$}. (g) $L =$ {$w ∈$ {$a,b$}$^* : n_a (w) = 2n_b(w) + 1$}.
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
monotonically increasing grammar
Which of the following is not a monotonically increasing grammar? (A) Context-sensitive grammar (B) Unrestricted grammar (C) Regular grammar (D) Context-free grammar
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
NIELIT 2016 MAR Scientist C - Section C: 14
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
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
NIELIT 2016 MAR Scientist C - Section C: 15
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
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
NIELIT 2016 MAR Scientist C - Section C: 32
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
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 in Theory of Computation Lakshman Patel RJIT 45 views
1 vote
2 answers
39
NIELIT 2017 OCT Scientific Assistant A (IT) - Section C: 9
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 [closed]
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.
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...