Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Theory of Computation:
Recent questions tagged theory-of-computation
0
votes
0
answers
1081
Peter Linz Edition 5 Exercise 8.1 Question 7(g) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w...
Rishi yadav
166
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
1082
Peter Linz Edition 5 Exercise 8.1 Question 7(f) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $$L = \{w:n_a(w) <n_b(w)<n_c(w)\}$$.
Rishi yadav
204
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
1083
Peter Linz Edition 5 Exercise 8.1 Question 7(e) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$...
Rishi yadav
269
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
1084
Peter Linz Edition 5 Exercise 8.1 Question 7(d) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.
Rishi yadav
181
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
2
answers
1085
Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\...
Rishi yadav
448
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
1086
Peter Linz Edition 5 Exercise 8.1 Question 7(b) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j: n\geq(j-1)^3\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j: n\geq(j-...
Rishi yadav
140
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
1
votes
0
answers
1087
Peter Linz Edition 5 Exercise 8.1 Question 7(a) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j : n\leq j^2\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j : n\leq j^2\}...
Rishi yadav
275
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
1088
Peter Linz Edition 5 Exercise 8.1 Question 6 (Page No. 212)
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.
Rishi yadav
297
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
1089
Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
Rishi yadav
237
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
context-free-language
+
–
0
votes
0
answers
1090
Peter Linz Edition 5 Exercise 8.1 Question 4 (Page No. 212)
Show that $L=\{w \in \{a,b,c\}^*:n_a^2(w) + n_b^2(w) = n_c^2(w)\}$ is not a context-free.
Show that $L=\{w \in \{a,b,c\}^*:n_a^2(w) + n_b^2(w) = n_c^2(w)\}$ is not a context-free.
Rishi yadav
142
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
pumping-lemma
+
–
0
votes
0
answers
1091
Peter Linz Edition 5 Exercise 8.1 Question 3 (Page No. 212)
Show that $L=\{ww^Rw:w\in\{a,b\}^*\}$ is not a context-free language.
Show that $L=\{ww^Rw:w\in\{a,b\}^*\}$ is not a context-free language.
Rishi yadav
173
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
+
–
0
votes
0
answers
1092
Peter Linz Edition 5 Exercise 8.1 Question 2 (Page No. 212)
Show that the language $L = \{a^n : n \text{ is a prime number}\}$ is not context-free.
Show that the language $L = \{a^n : n \text{ is a prime number}\}$ is not context-free.
Rishi yadav
124
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
+
–
0
votes
0
answers
1093
Peter Linz Edition 5 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L = \{w\in \{a,b,c\}^*: n_a(w) = n_b(w) \leq n_c(w)\}$ is not context-free.
Show that the language $L = \{w\in \{a,b,c\}^*: n_a(w) = n_b(w) \leq n_c(w)\}$is not context-free.
Rishi yadav
140
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
+
–
2
votes
1
answer
1094
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.2Suppose that $G = (V, T,...
Naveen Kumar 3
361
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
1095
Peter Linz Edition 4 Exercise 5.2 Question 19 (Page No. 145)
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar in which every $A ∈ V$ occurs on the left side of at most one production. Then $G$ is unambiguous.
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar in which every $A ∈ V$ occurs on the left side of at most one production. Then $G$ is unam...
Naveen Kumar 3
204
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
ambiguous
+
–
0
votes
1
answer
1096
Peter Linz Edition 4 Exercise 5.2 Question 18 (Page No. 145)
Is the string $aabbababb$ in the language generated by the grammar $S → aSS|b$? Show that the grammar with productions $S\rightarrow aAb|\lambda,$ $A\rightarrow aAb|\lambda$ is unambiguous.
Is the string $aabbababb$ in the language generated by the grammar $S → aSS|b$?Show that the grammar with productions$S\rightarrow aAb|\lambda,$$A\rightarrow aAb|\lambd...
Naveen Kumar 3
321
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
ambiguous
+
–
0
votes
1
answer
1097
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 ...
Naveen Kumar 3
394
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
parsing
+
–
0
votes
0
answers
1098
Peter Linz Edition 4 Exercise 5.2 Question 16 (Page No. 145)
Show that the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A|\lambda.$ is unambiguous.
Show that the grammar with productions$S\rightarrow aAB,$$A\rightarrow bBb,$$B\rightarrow A|\lambda.$ is unambiguous.
Naveen Kumar 3
275
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
+
–
0
votes
1
answer
1099
Peter Linz Edition 4 Exercise 5.2 Question 15 (Page No. 145)
Show that the grammar with productions $S\rightarrow SS,$ $S\rightarrow \lambda,$ $S\rightarrow aSb,$ $S\rightarrow bSa.$ is ambiguous.
Show that the grammar with productions$S\rightarrow SS,$$S\rightarrow \lambda,$$S\rightarrow aSb,$$S\rightarrow bSa.$is ambiguous.
Naveen Kumar 3
322
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
+
–
0
votes
1
answer
1100
Peter Linz Edition 4 Exercise 5.2 Question 14 (Page No. 145)
Show that the grammar $S\rightarrow aSb|SS|\lambda$ is ambiguous, but that the language denoted by it is not.
Show that the grammar $S\rightarrow aSb|SS|\lambda$ is ambiguous, but that the language denoted by it is not.
Naveen Kumar 3
273
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
+
–
0
votes
1
answer
1101
Peter Linz Edition 4 Exercise 5.2 Question 13 (Page No. 145)
Show that the following grammar is ambiguous. $S\rightarrow aSbS|bSaS|\lambda$
Show that the following grammar is ambiguous. $S\rightarrow aSbS|bSaS|\lambda$
Naveen Kumar 3
211
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
+
–
0
votes
0
answers
1102
Peter Linz Edition 4 Exercise 5.2 Question 12 (Page No. 145)
Show that the language $L =$ {$ww^R : w ∈$ {$a,b$}$^*$} is not inherently ambiguous.
Show that the language $L =$ {$ww^R : w ∈$ {$a,b$}$^*$} is not inherently ambiguous.
Naveen Kumar 3
143
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
inherently-ambiguous
grammar
+
–
0
votes
0
answers
1103
Peter Linz Edition 4 Exercise 5.2 Question 11 (Page No. 145)
Is it possible for a regular grammar to be ambiguous?
Is it possible for a regular grammar to be ambiguous?
Naveen Kumar 3
149
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
ambiguous
+
–
0
votes
0
answers
1104
Peter Linz Edition 4 Exercise 5.2 Question 10 (Page No. 145)
Give an unambiguous grammar that generates the set of all regular expressions on $Σ =$ {$a,b$}.
Give an unambiguous grammar that generates the set of all regular expressions on $Σ =$ {$a,b$}.
Naveen Kumar 3
398
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
regular-expression
+
–
0
votes
0
answers
1105
Peter Linz Edition 4 Exercise 5.2 Question 9 (Page No. 145)
Show that a regular language cannot be inherently ambiguous.
Show that a regular language cannot be inherently ambiguous.
Naveen Kumar 3
177
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
inherently-ambiguous
grammar
+
–
0
votes
0
answers
1106
Peter Linz Edition 4 Exercise 5.2 Question 8 (Page No. 145)
Give the derivation tree for (((a + b) * c)) + a + b, using the grammar with productions $E\rightarrow I,$ $E\rightarrow E+E,$ $E\rightarrow E*E,$ $E\rightarrow (E),$ $I\rightarrow a|b|c.$
Give the derivation tree for (((a + b) * c)) + a + b, using the grammar with productions$E\rightarrow I,$$E\rightarrow E+E,$$E\rightarrow E*E,$$E\rightarrow (E),$$I\right...
Naveen Kumar 3
164
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
+
–
0
votes
1
answer
1107
Peter Linz Edition 4 Exercise 5.2 Question 7 (Page No. 145)
Construct an unambiguous grammar equivalent to the grammar in Exercise 6.
Construct an unambiguous grammar equivalent to the grammar in Exercise 6.
Naveen Kumar 3
220
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
+
–
1
votes
1
answer
1108
Peter Linz Edition 4 Exercise 5.2 Question 6 (Page No. 145)
Show that the following grammar is ambiguous. $S\rightarrow AB|aaB,$ $A\rightarrow a|Aa,$ $B\rightarrow b.$
Show that the following grammar is ambiguous.$S\rightarrow AB|aaB,$$A\rightarrow a|Aa,$$B\rightarrow b.$
Naveen Kumar 3
210
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
+
–
0
votes
1
answer
1109
Peter Linz Edition 4 Exercise 5.2 Question 5 (Page No. 145)
Let $G = (V, T, S, P)$ be an s-grammar. Give an expression for the maximum size of $P$ in terms of $|V|$ and $|T|$.
Let $G = (V, T, S, P)$ be an s-grammar. Give an expression for the maximum size of $P$ in terms of $|V|$ and $|T|$.
Naveen Kumar 3
190
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
+
–
0
votes
0
answers
1110
Peter Linz Edition 4 Exercise 5.2 Question 4 (Page No. 145)
Show that every s-grammar is unambiguous.
Show that every s-grammar is unambiguous.
Naveen Kumar 3
199
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
ambiguous
grammar
+
–
Page:
« prev
1
...
32
33
34
35
36
37
38
39
40
41
42
...
155
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register