Dark Mode

Recent questions tagged peter-linz-edition4

0 votes

0 answers

61

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.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

147 views

0 votes

0 answers

62

Peter Linz Edition 4 Exercise 6.2 Question 12 (Page No. 170)
Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

107 views

0 votes

0 answers

63

Peter Linz Edition 4 Exercise 6.2 Question 11 (Page No. 170)
Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

120 views

0 votes

0 answers

64

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.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

137 views

0 votes

0 answers

65

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

89 views

0 votes

0 answers

66

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)$.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

130 views

0 votes

0 answers

67

Peter Linz Edition 4 Exercise 6.2 Question 7 (Page No. 169)
Draw the dependency graph for the grammar in Exercise 4.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

139 views

1 vote

0 answers

68

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.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

837 views

0 votes

0 answers

69

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.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

171 views

0 votes

0 answers

70

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.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

137 views

0 votes

0 answers

71

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.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

109 views

0 votes

0 answers

72

Peter Linz Edition 4 Exercise 6.2 Question 2 (Page No. 169)
Convert the grammar $S\rightarrow aSb|ab$ into Chomsky normal form.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

90 views

0 votes

0 answers

73

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.

Naveen Kumar 3 asked in Theory of Computation Apr 19, 2019

by Naveen Kumar 3

116 views

0 votes

0 answers

74

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.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

102 views

0 votes

0 answers

75

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.$

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

102 views

0 votes

0 answers

76

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).$

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

95 views

0 votes

0 answers

77

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.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

154 views

0 votes

0 answers

78

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?

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

415 views

0 votes

0 answers

79

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.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

231 views

0 votes

0 answers

80

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.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

112 views

0 votes

0 answers

81

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.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

123 views

1 vote

0 answers

82

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.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

175 views

0 votes

0 answers

83

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

259 views

1 vote

0 answers

84

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.

Naveen Kumar 3 asked in Theory of Computation Apr 17, 2019

by Naveen Kumar 3

221 views

0 votes

0 answers

85

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) –$ {$λ$}.

Naveen Kumar 3 asked in Theory of Computation Apr 15, 2019

by Naveen Kumar 3

147 views

0 votes

1 answer

86

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?

Naveen Kumar 3 asked in Theory of Computation Apr 15, 2019

by Naveen Kumar 3

158 views

0 votes

0 answers

87

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 15, 2019

by Naveen Kumar 3

117 views

0 votes

0 answers

88

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.

Naveen Kumar 3 asked in Theory of Computation Apr 15, 2019

by Naveen Kumar 3

120 views

1 vote

1 answer

89

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?

Naveen Kumar 3 asked in Theory of Computation Apr 15, 2019

by Naveen Kumar 3

440 views

1 vote

1 answer

90

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.$

Naveen Kumar 3 asked in Theory of Computation Apr 15, 2019

by Naveen Kumar 3

182 views

Page:

« prev
1
2
3
4
5
6
7
8
...
13
next »

Recent questions tagged peter-linz-edition4