Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz
0
votes
0
answers
61
Peter Linz Edition 4 Exercise 6.3 Question 3 (Page No. 173)
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.
Naveen Kumar 3
133
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
62
Peter Linz Edition 4 Exercise 6.3 Question 2 (Page No. 173)
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ ...
Naveen Kumar 3
165
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
63
Peter Linz Edition 4 Exercise 6.3 Question 1 (Page No. 172)
Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in the language generated by the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$
Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in thelanguage generated by the grammar with productions $S\rightar...
Naveen Kumar 3
170
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
64
Peter Linz Edition 4 Exercise 6.2 Question 16 (Page No. 170)
“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.
“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.
Naveen Kumar 3
129
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
65
Peter Linz Edition 4 Exercise 6.2 Question 15 (Page No. 170)
A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ $A\rightarrow aB,$ $A\rightarrow a,$ where $A, B, C ∈ V$ and $a ∈ T$. Convert the grammar ... $S\rightarrow aSA,$ $A\rightarrow bABC,$ $B\rightarrow b,$ $C\rightarrow aBC$ into two-standard form.
A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ ...
Naveen Kumar 3
157
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
66
Peter Linz Edition 4 Exercise 6.2 Question 14 (Page No. 170)
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?
Naveen Kumar 3
372
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
+
–
0
votes
0
answers
67
Peter Linz Edition 4 Exercise 6.2 Question 13 (Page No. 170)
Convert the grammar $S\rightarrow ABb|a,$ $A\rightarrow aaA|B,$ $B\rightarrow bAb$ into Greibach normal form.
Convert the grammar $S\rightarrow ABb|a,$ $A\rightarrow aaA|B,$ $B\rightarrow bAb$into Greibach normal form.
Naveen Kumar 3
227
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
+
–
0
votes
0
answers
68
Peter Linz Edition 4 Exercise 6.2 Question 12 (Page No. 170)
Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.
Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.
Naveen Kumar 3
171
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
+
–
0
votes
0
answers
69
Peter Linz Edition 4 Exercise 6.2 Question 11 (Page No. 170)
Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$
Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$
Naveen Kumar 3
196
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
+
–
0
votes
0
answers
70
Peter Linz Edition 4 Exercise 6.2 Question 10 (Page No. 170)
Convert the grammar $S\rightarrow aSb|bSa|a|b$ into Greibach normal form.
Convert the grammar $S\rightarrow aSb|bSa|a|b$ into Greibach normal form.
Naveen Kumar 3
192
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
+
–
0
votes
0
answers
71
Peter Linz Edition 4 Exercise 6.2 Question 9 (Page No. 170)
Show that for every context-free grammar $G = (V, T, S, P)$ there is an equivalent one in which all productions have the form $A → aBC,$ or $A → λ,$ where $a∈Σ$ $\cup$ {$\lambda$} , $A,B,C∈V$.
Show that for every context-free grammar $G = (V, T, S, P)$ there is an equivalent one in which all productions have the form $A → aBC,$or ...
Naveen Kumar 3
124
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
72
Peter Linz Edition 4 Exercise 6.2 Question 8 (Page No. 169)
A linear language is one for which there exists a linear grammar [A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable. Clearly, a regular grammar is always ... $A\rightarrow a,$ where $a∈ T$ , $A, B∈ V,$ such that $L = L (G)$.
A linear language is one for which there exists a linear grammar[A linear grammar is a grammar in which at most one variable can occur on the right side of any production...
Naveen Kumar 3
184
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
73
Peter Linz Edition 4 Exercise 6.2 Question 7 (Page No. 169)
Draw the dependency graph for the grammar in Exercise 4.
Draw the dependency graph for the grammar in Exercise 4.
Naveen Kumar 3
277
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
0
answers
74
Peter Linz Edition 4 Exercise 6.2 Question 6 (Page No. 169)
Let $G = (V, T, S, P)$ be any context-free grammar without any $λ$-productions or unit-productions. Let $k$ be the maximum number of symbols on the right of any production in $P$. Show that there is an equivalent grammar in Chomsky normal form with no more than $(k-1)|P|+|T|$ production rules.
Let $G = (V, T, S, P)$ be any context-free grammar without any $λ$-productions or unit-productions.Let $k$ be the maximum number of symbols on the right of any productio...
Naveen Kumar 3
1.0k
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
75
Peter Linz Edition 4 Exercise 6.2 Question 5 (Page No. 169)
Convert the grammar with productions $S\rightarrow AB|aB,$ $A\rightarrow aab|\lambda,$ $B\rightarrow bbA$ into Chomsky normal form.
Convert the grammar with productions$S\rightarrow AB|aB,$$A\rightarrow aab|\lambda,$$B\rightarrow bbA$ into Chomsky normal form.
Naveen Kumar 3
271
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
76
Peter Linz Edition 4 Exercise 6.2 Question 4 (Page No. 169)
Transform the grammar with productions $S\rightarrow abAB,$ $A\rightarrow bAB|\lambda,$ $B\rightarrow BAa|A|\lambda$ into Chomsky normal form.
Transform the grammar with productions$S\rightarrow abAB,$$A\rightarrow bAB|\lambda,$$B\rightarrow BAa|A|\lambda$ into Chomsky normal form.
Naveen Kumar 3
231
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
77
Peter Linz Edition 4 Exercise 6.2 Question 3 (Page No. 169)
Transform the grammar $S\rightarrow aSaA|A, A\rightarrow abA|b$ into Chomsky normal form.
Transform the grammar $S\rightarrow aSaA|A, A\rightarrow abA|b$ into Chomsky normal form.
Naveen Kumar 3
173
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
78
Peter Linz Edition 4 Exercise 6.2 Question 2 (Page No. 169)
Convert the grammar $S\rightarrow aSb|ab$ into Chomsky normal form.
Convert the grammar $S\rightarrow aSb|ab$ into Chomsky normal form.
Naveen Kumar 3
122
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
79
Peter Linz Edition 4 Exercise 6.2 Question 1 (Page No. 169)
Provide the details of the proof of Theorem 6.6. Theorem 6.6 Any context-free grammar $G = (V, T, S, P)$ with $λ ∉ L (G)$ has an equivalent grammar $\widehat G=(\widehat V,\widehat T,S,\widehat P)$ in Chomsky normal form.
Provide the details of the proof of Theorem 6.6.Theorem 6.6Any context-free grammar $G = (V, T, S, P)$ with $λ ∉ L (G)$ has an equivalent grammar $\widehat G=(\widehat...
Naveen Kumar 3
160
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
80
Peter Linz Edition 4 Exercise 6.1 Question 25 (Page No. 164)
Prove the following counterpart of Exercise 23. Let the set of productions involving the variable $A$ on the left be divided into two disjoint subsets $A\rightarrow x_1A|x_2A|...|x_nA,$ and, $A\rightarrow y_1|y_2|...|y_m,$ where $A$ is not a ... $Z\rightarrow x_i|Zx_i,$ $i=1,2,3, ,n.$ is equivalent to the original grammar.
Prove the following counterpart of Exercise 23. Let the set of productions involving the variable $A$ on the left be divided into two disjoint subsets ...
Naveen Kumar 3
132
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
81
Peter Linz Edition 4 Exercise 6.1 Question 24 (Page No. 164)
Use the result of the preceding exercise to rewrite the grammar $A\rightarrow Aa|aBc|\lambda,$ $B\rightarrow Bb|bc$ so that it no longer has productions of the form $A → Ax$ or $B → Bx.$
Use the result of the preceding exercise to rewrite the grammar$A\rightarrow Aa|aBc|\lambda,$$B\rightarrow Bb|bc$so that it no longer has productions of the form $A → A...
Naveen Kumar 3
185
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
82
Peter Linz Edition 4 Exercise 6.1 Question 23 (Page No. 163)
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar. Divide the set of productions whose left sides are some given variable (say, $A$), into two disjoint subsets $A\rightarrow Ax_1|Ax_2|...|Ax_n,$ $A\rightarrow y_1|y_2|...|y_m,$ ... $Z\rightarrow x_i|x_iZ,$ $i=1,2,3, ,n.$ Then $L (G) = L ( \widehat G).$
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar. Divide the set of productions whose left sides are some given variable (say, $A$), into two...
Naveen Kumar 3
148
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
83
Peter Linz Edition 4 Exercise 6.1 Question 22 (Page No. 163)
A context-free grammar $G$ is said to be minimal for a given language $L$ if $complexity (G) ≤ complexity (\widehat G)$ for any $\widehat{G}$ generating $L$. Show by example that the removal of useless productions does not necessarily produce a minimal grammar.
A context-free grammar $G$ is said to be minimal for a given language $L$ if $complexity (G) ≤ complexity (\widehat G)$ for any $\widehat{G}$ generating $L$. Show by ex...
Naveen Kumar 3
213
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
84
Peter Linz Edition 4 Exercise 6.1 Question 21 (Page No. 163)
It is possible to define the term simplification precisely by introducing the concept of complexity of a grammar. This can be done in many ways; one of them is through the length of all the strings giving the production rules ... the complexity in this sense. What can you say about the removal of $λ$-productions and unit-productions?
It is possible to define the term simplification precisely by introducing the concept of complexity of a grammar. This can be done in many ways; one of them is through th...
Naveen Kumar 3
455
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
85
Peter Linz Edition 4 Exercise 6.1 Question 20 (Page No. 163)
Consider the procedure suggested in Theorem 6.2 for the removal of useless productions. Reverse the order of the two parts, first eliminating variables that cannot be reached from S, then removing those that do not yield a terminal string. Does the new procedure still work correctly? If so, prove it. If not, give a counterexample.
Consider the procedure suggested in Theorem 6.2 for the removal of useless productions. Reverse the order of the two parts, first eliminating variables that cannot be rea...
Naveen Kumar 3
313
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
86
Peter Linz Edition 4 Exercise 6.1 Question 19 (Page No. 163)
Suppose that a context-free grammar $G = (V, T, S, P)$ has a production of the form $A → xy,$ where $x,y∈ (V\cup T)^+$. Prove that if this rule is replaced by $A\rightarrow By, B\rightarrow x,$ where $B ∉ V,$ then the resulting grammar is equivalent to the original one.
Suppose that a context-free grammar $G = (V, T, S, P)$ has a production of the form $A → xy,$ where $x,y∈ (V\cup T)^+$. Prove that if this rule is replaced by $A\righ...
Naveen Kumar 3
145
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
87
Peter Linz Edition 4 Exercise 6.1 Question 18 (Page No. 162)
Justify the claim made in the proof of Theorem 6.1 that the variable $B$ can be replaced as soon as it appears.
Justify the claim made in the proof of Theorem 6.1 that the variable $B$ can be replaced as soon asit appears.
Naveen Kumar 3
179
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
0
answers
88
Peter Linz Edition 4 Exercise 6.1 Question 17 (Page No. 162)
Show that if a grammar has no $λ$-productions and no unit-productions, then the removal of useless productions by the construction of Theorem 6.2 does not introduce any such productions. Theorem 6.2 Let $G = (V, T, S, P )$ ... that does not contain any useless variables or productions.
Show that if a grammar has no $λ$-productions and no unit-productions, then the removal of useless productions by the construction of Theorem 6.2 does not introduce any ...
Naveen Kumar 3
224
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
89
Peter Linz Edition 4 Exercise 6.1 Question 16 (Page No. 162)
Let $G$ be a grammar without $λ$-productions, but possibly with some unit-productions. Show that the construction of Theorem 6.4 does not then introduce any $λ$-productions. Theorem 6.4 Let $G = (V, T, S, P )$ be any context- ... $G$.
Let $G$ be a grammar without $λ$-productions, but possibly with some unit-productions. Show thatthe construction of Theorem 6.4 does not then introduce any $λ$-producti...
Naveen Kumar 3
327
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
0
answers
90
Peter Linz Edition 4 Exercise 6.1 Question 15 (Page No. 162)
Give an example of a situation in which the removal of $λ$-productions introduces previously nonexistent unit-productions.
Give an example of a situation in which the removal of $λ$-productions introduces previouslynonexistent unit-productions.
Naveen Kumar 3
280
views
Naveen Kumar 3
asked
Apr 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
Page:
« prev
1
2
3
4
5
6
7
8
...
20
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register