Register
Filter

Questions by Naveen Kumar 3

246
views
0 answers
0 votes
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.
183
views
0 answers
0 votes
Peter Linz Edition 4 Exercise 6.2 Question 12 (Page No. 170)
Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.
214
views
0 answers
0 votes
Peter Linz Edition 4 Exercise 6.2 Question 11 (Page No. 170)
Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$
210
views
0 answers
0 votes
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.
138
views
0 answers
0 votes
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 ...
218
views
0 answers
0 votes
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...
323
views
0 answers
0 votes
Peter Linz Edition 4 Exercise 6.2 Question 7 (Page No. 169)
Draw the dependency graph for the grammar in Exercise 4.
1.1k
views
0 answers
1 votes
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 productio...
297
views
0 answers
0 votes
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.
256
views
0 answers
0 votes
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.
181
views
0 answers
0 votes
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.
134
views
0 answers
0 votes
Peter Linz Edition 4 Exercise 6.2 Question 2 (Page No. 169)
Convert the grammar $S\rightarrow aSb|ab$ into Chomsky normal form.
172
views
0 answers
0 votes
Peter Linz Edition 4 Exercise 6.2 Question 1 (Page No. 169)
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...
146
views
0 answers
0 votes
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 ...
199
views
0 answers
0 votes
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 → A...
164
views
0 answers
0 votes
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...
235
views
0 answers
0 votes
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 ex...
476
views
0 answers
0 votes
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 th...
335
views
0 answers
0 votes
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 rea...
175
views
0 answers
0 votes
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\righ...
Page: