Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz
0
votes
0
answers
121
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
122
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
123
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
124
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
125
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
323
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
126
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
127
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
128
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
129
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
130
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
131
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
132
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
133
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
134
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
135
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
191
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
+
–
0
votes
0
answers
136
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
+
–
0
votes
1
answer
137
Peter Linz Edition 4 Exercise 5.2 Question 3 (Page No. 144)
Find an s-grammar for $L =$ {$a^nb^{n+1} : n ≥ 2$}.
Find an s-grammar for $L =$ {$a^nb^{n+1} : n ≥ 2$}.
Naveen Kumar 3
361
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
+
–
0
votes
1
answer
138
Peter Linz Edition 4 Exercise 5.2 Question 2 (Page No. 144)
Find an s-grammar for $L =$ {$a^nb^n : n ≥ 1$}.
Find an s-grammar for $L =$ {$a^nb^n : n ≥ 1$}.
Naveen Kumar 3
449
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
+
–
0
votes
1
answer
139
Peter Linz Edition 4 Exercise 5.2 Question 1 (Page No. 144)
Find an s-grammar for $L (aaa^*b + b)$.
Find an s-grammar for $L (aaa^*b + b)$.
Naveen Kumar 3
366
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
grammar
+
–
0
votes
0
answers
140
Peter Linz Edition 4 Exercise 5.1 Question 27 (Page No. 135)
Let $G = (V,T,S,P)$ be a context-free grammar such that every one of its productions is of the form $A → v,$ with $|v| = k > 1.$ Show that the derivation tree for any $w ∈ L(G)$ has a height $h$ such that $\log_{k}|w|\leq h\leq \frac{(|w|-1)}{k-1}$.
Let $G = (V,T,S,P)$ be a context-free grammar such that every one of its productions is of the form $A → v,$ with $|v| = k 1.$ Show that the derivation tree for any $w...
Naveen Kumar 3
256
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
141
Peter Linz Edition 4 Exercise 5.1 Question 26 (Page No. 135)
Find a linear grammar for the language $L=$ {$a^nb^m:n\neq m$}.
Find a linear grammar for the language $L=$ {$a^nb^m:n\neq m$}.
Naveen Kumar 3
133
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
142
Peter Linz Edition 4 Exercise 5.1 Question 25 (Page No. 135)
Prove that if $G$ is a context-free grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a derivation tree.
Prove that if $G$ is a context-free grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a deriva...
Naveen Kumar 3
152
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
143
Peter Linz Edition 4 Exercise 5.1 Question 24 (Page No. 135)
Find a context-free grammar that can generate all the production rules for context-free grammars with $T =$ {$a, b$} and $V =$ {$A, B, C$}.
Find a context-free grammar that can generate all the production rules for context-free grammars with $T =$ {$a, b$} and $V =$ {$A, B, C$}.
Naveen Kumar 3
135
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
144
Peter Linz Edition 4 Exercise 5.1 Question 23 (Page No. 135)
Find a context-free grammar for the set of all regular expressions on the alphabet {$a, b$}.
Find a context-free grammar for the set of all regular expressions on the alphabet {$a, b$}.
Naveen Kumar 3
121
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
145
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 sit...
Naveen Kumar 3
370
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
146
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 i...
Naveen Kumar 3
585
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
147
Peter Linz Edition 4 Exercise 5.1 Question 20 (Page No. 135)
Consider the grammar with productions $S\rightarrow aaB,$ $A\rightarrow bBb|\lambda,$ $B\rightarrow Aa.$ Show that the string $aabbabba$ is not in the language generated by this grammar.
Consider the grammar with productions$S\rightarrow aaB,$$A\rightarrow bBb|\lambda,$$B\rightarrow Aa.$Show that the string $aabbabba$ is not in the language generated by t...
Naveen Kumar 3
221
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
1
answer
148
Peter Linz Edition 4 Exercise 5.1 Question 19 (Page No. 134)
Show a derivation tree for the string $aabbbb$ with the grammar $S\rightarrow AB|\lambda,$ $A\rightarrow aB,$ $B\rightarrow Sb.$ Give a verbal description of the language generated by this grammar.
Show a derivation tree for the string $aabbbb$ with the grammar$S\rightarrow AB|\lambda,$$A\rightarrow aB,$$B\rightarrow Sb.$Give a verbal description of the language gen...
Naveen Kumar 3
477
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
149
Peter Linz Edition 4 Exercise 5.1 Question 18 (Page No. 134)
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is context-free.
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is context-free.
Naveen Kumar 3
225
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
150
Peter Linz Edition 4 Exercise 5.1 Question 17 (Page No. 134)
Show that the complement of the language $L =$ {$a^nb^mc^k : k = n + m$} is context-free.
Show that the complement of the language $L =$ {$a^nb^mc^k : k = n + m$} is context-free.
Naveen Kumar 3
149
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
...
20
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register