Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz
0
votes
0
answers
91
Peter Linz Edition 4 Exercise 6.1 Question 14 (Page No. 162)
Suppose that $G$ is a context-free grammar for which $λ ∈ L (G)$. Show that if we apply the construction in Theorem 6.3, we obtain a new grammar $\widehat{G}$ such that $L(\widehat{G} ) = L (G) –$ {$λ$}.
Suppose that $G$ is a context-free grammar for which $λ ∈ L (G)$. Show that if we apply theconstruction in Theorem 6.3, we obtain a new grammar $\widehat{G}$ such that...
Naveen Kumar 3
198
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
92
Peter Linz Edition 4 Exercise 6.1 Question 12 (Page No. 162)
Remove $λ$-productions from the grammar with productions $S\rightarrow aSb|SS|\lambda.$ What language does the resulting grammar generate?
Remove $λ$-productions from the grammar with productions $S\rightarrow aSb|SS|\lambda.$What language does the resulting grammar generate?
Naveen Kumar 3
250
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
93
Peter Linz Edition 4 Exercise 6.1 Question 11 (Page No. 162)
Complete the proof of Theorem 6.4. Theorem 6.4 Let $G = (V, T, S, P )$ be any context-free grammar without $λ$-productions. Then there exists a context-free grammar $\widehat{G}=(\widehat{V},\widehat{T},S,\widehat{P})$ that does not have any unit-productions and that is equivalent to $G$.
Complete the proof of Theorem 6.4.Theorem 6.4Let $G = (V, T, S, P )$ be any context-free grammar without $λ$-productions. Then there exists a context-free grammar $\wide...
Naveen Kumar 3
279
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
94
Peter Linz Edition 4 Exercise 6.1 Question 10 (Page No. 162)
Complete the proof of Theorem 6.3. Theorem 6.3 Let $G$ be any context-free grammar with $λ$ not in $L (G)$. Then there exists an equivalent grammar $\widehat{G}$ having no $λ$-productions.
Complete the proof of Theorem 6.3.Theorem 6.3Let $G$ be any context-free grammar with $λ$ not in $L (G)$. Then there exists an equivalent grammar $\widehat{G}$having no ...
Naveen Kumar 3
270
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
2
votes
1
answer
95
Peter Linz Edition 4 Exercise 6.1 Question 8 (Page No. 162)
Remove all unit-productions, all useless productions, and all λ-productions from the grammar $S\rightarrow aA|aBB,$ $A\rightarrow aaA|\lambda,$ $B\rightarrow bB|bbC,$ $C\rightarrow B.$ What language does this grammar generate?
Remove all unit-productions, all useless productions, and all λ-productions from the grammar$S\rightarrow aA|aBB,$$A\rightarrow aaA|\lambda,$$B\rightarrow bB|bbC,$$C\rig...
Naveen Kumar 3
2.5k
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
1
votes
1
answer
96
Peter Linz Edition 4 Exercise 6.1 Question 7 (Page No. 162)
Eliminate all λ-productions from $S\rightarrow AaB|aaB,$ $A\rightarrow \lambda,$ $B\rightarrow bbA|\lambda.$
Eliminate all λ-productions from$S\rightarrow AaB|aaB,$$A\rightarrow \lambda,$$B\rightarrow bbA|\lambda.$
Naveen Kumar 3
405
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
2
votes
2
answers
97
Peter Linz Edition 4 Exercise 6.1 Question 6 (Page No. 161)
Eliminate useless productions from $S\rightarrow a|aA|B|C,$ $A\rightarrow aB|\lambda,$ $B\rightarrow Aa,$ $C\rightarrow cCD,$ $D\rightarrow ddd.$
Eliminate useless productions from$S\rightarrow a|aA|B|C,$$A\rightarrow aB|\lambda,$$B\rightarrow Aa,$$C\rightarrow cCD,$$D\rightarrow ddd.$
Naveen Kumar 3
513
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
1
answer
98
Peter Linz Edition 4 Exercise 6.1 Question 5 (Page No. 161)
Eliminate all useless productions from the grammar $S\rightarrow aS|AB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?
Eliminate all useless productions from the grammar$S\rightarrow aS|AB,$$A\rightarrow bA,$$B\rightarrow AA.$What language does this grammar generate?
Naveen Kumar 3
381
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
context-free-grammar
context-free-language
+
–
0
votes
0
answers
99
Peter Linz Edition 4 Exercise 6.1 Question 4 (Page No. 161)
In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?
In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?
Naveen Kumar 3
287
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
100
Peter Linz Edition 4 Exercise 6.1 Question 3 (Page No. 161)
Show that the two grammars $S\rightarrow abAB|ba,$ $A\rightarrow aaa,$ $B\rightarrow aA|bb$ and $S\rightarrow abAaA|abAbb|ba,$ $A\rightarrow aaa$ are equivalent.
Show that the two grammars$S\rightarrow abAB|ba,$$A\rightarrow aaa,$$B\rightarrow aA|bb$ and$S\rightarrow abAaA|abAbb|ba,$$A\rightarrow aaa$ ...
Naveen Kumar 3
187
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
101
Peter Linz Edition 4 Exercise 6.1 Question 2 (Page No. 161)
Show a derivation tree for the string $ababbac$, using grammar with productions $A\rightarrow a|aaA|abBC,$ $B\rightarrow abbA|b.$ also show the derivation tree for grammar with productions $A\rightarrow a|aaA|ababbAc|abbc,$ $B\rightarrow abbA|b.$
Show a derivation tree for the string $ababbac$, using grammar with productions$A\rightarrow a|aaA|abBC,$$B\rightarrow abbA|b.$also show the derivation tree for grammar w...
Naveen Kumar 3
146
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
102
Peter Linz Edition 4 Exercise 6.1 Question 1 (Page No. 161)
Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$ implies $S\overset{*}{\Rightarrow}_{G} w$. Theorem 6.1 Let $G = (V, T, S, P)$ be a context-free grammar. Suppose that $P$ ... $P$, and adding to it $A\rightarrow x_1y_1x_2|x_1y_2x_2|...|x_1y_nx_2.$ Then, $L(\widehat{G})=L(G)$.
Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$implies $S\overset{*}{\Rightarrow}_{...
Naveen Kumar 3
532
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
103
Peter Linz Edition 5 Exercise 8.1 Question 7(k) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not ...
Rishi yadav
368
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
1
answer
104
Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prime}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prim...
Rishi yadav
354
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
105
Peter Linz Edition 5 Exercise 8.1 Question 7(i) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prime}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prim...
Rishi yadav
198
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
106
Peter Linz Edition 5 Exercise 8.1 Question 7(h) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\...
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
107
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
179
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
108
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
225
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
109
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
284
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
110
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
195
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
111
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
518
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
112
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
145
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
113
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
285
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
114
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
314
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
115
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
241
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
116
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
155
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
117
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
192
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
118
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
141
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
119
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
145
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
120
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
371
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
...
20
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register