Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged context-free-grammar
0
votes
0
answers
121
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
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
122
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
132
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
123
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
164
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
124
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
385
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
125
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
236
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
126
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
175
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
127
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
210
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
128
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
198
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
129
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
131
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
130
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
192
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
131
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
296
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
132
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.1k
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
133
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
280
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
134
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
240
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
135
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
174
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
136
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
125
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
137
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
163
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
138
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
140
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
139
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
193
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
140
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
160
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
141
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
229
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
142
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
463
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
143
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
322
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
144
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
155
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
145
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
186
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
146
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
226
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
147
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
333
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
148
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
196
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
149
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
248
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
150
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
278
views
Naveen Kumar 3
asked
Apr 15, 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
10
...
12
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register