Dark Mode

Recent questions tagged peter-linz-edition4

1 vote

2 answers

91

Peter Linz Edition 4 Exercise 6.1 Question 6 (Page No. 161)
Eliminate useless productions from $S\rightarrow a|aA|B|C,$ $A\rightarrow aB|\lambda,$ $B\rightarrow Aa,$ $C\rightarrow cCD,$ $D\rightarrow ddd.$

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

by Naveen Kumar 3

308 views

1 vote

1 answer

92

Peter Linz Edition 4 Exercise 6.1 Question 5 (Page No. 161)
Eliminate all useless productions from the grammar $S\rightarrow aS|AB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?

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

by Naveen Kumar 3

255 views

0 votes

0 answers

93

Peter Linz Edition 4 Exercise 6.1 Question 4 (Page No. 161)
In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?

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

by Naveen Kumar 3

214 views

0 votes

0 answers

94

Peter Linz Edition 4 Exercise 6.1 Question 3 (Page No. 161)
Show that the two grammars $S\rightarrow abAB|ba,$ $A\rightarrow aaa,$ $B\rightarrow aA|bb$ and $S\rightarrow abAaA|abAbb|ba,$ $A\rightarrow aaa$ are equivalent.

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

by Naveen Kumar 3

129 views

0 votes

0 answers

95

Peter Linz Edition 4 Exercise 6.1 Question 2 (Page No. 161)
Show a derivation tree for the string $ababbac$, using grammar with productions $A\rightarrow a|aaA|abBC,$ $B\rightarrow abbA|b.$ also show the derivation tree for grammar with productions $A\rightarrow a|aaA|ababbAc|abbc,$ $B\rightarrow abbA|b.$

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

by Naveen Kumar 3

90 views

0 votes

0 answers

96

Peter Linz Edition 4 Exercise 6.1 Question 1 (Page No. 161)
Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$ implies $S\overset{*}{\Rightarrow}_{G} w$. Theorem 6.1 Let $G = (V, T, S, P)$ be a context-free grammar. Suppose that $P$ ... $P$, and adding to it $A\rightarrow x_1y_1x_2|x_1y_2x_2|...|x_1y_nx_2.$ Then, $L(\widehat{G})=L(G)$.

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

by Naveen Kumar 3

419 views

2 votes

1 answer

97

Peter Linz Edition 4 Exercise 5.2 Question 20 (Page No. 145)
Find a grammar equivalent to $S\rightarrow aAB, A\rightarrow bBb, B\rightarrow A|\lambda$ that satisfies the conditions of Theorem 5.2. Theorem 5.2 Suppose that $G = (V, T, S, P)$ is a context-free grammar that does not have ... algorithm which, for any $w ∈ Σ^*,$ either produces a parsing of $w$ or tells us that no parsing is possible.

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

by Naveen Kumar 3

286 views

0 votes

0 answers

98

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.

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

by Naveen Kumar 3

133 views

0 votes

1 answer

99

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.

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

by Naveen Kumar 3

230 views

0 votes

1 answer

100

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?

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

by Naveen Kumar 3

245 views

0 votes

0 answers

101

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.

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

by Naveen Kumar 3

202 views

0 votes

1 answer

102

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.

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

by Naveen Kumar 3

239 views

0 votes

1 answer

103

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.

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

by Naveen Kumar 3

193 views

0 votes

1 answer

104

Peter Linz Edition 4 Exercise 5.2 Question 13 (Page No. 145)
Show that the following grammar is ambiguous. $S\rightarrow aSbS|bSaS|\lambda$

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

by Naveen Kumar 3

150 views

0 votes

0 answers

105

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.

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

by Naveen Kumar 3

111 views

0 votes

0 answers

106

Peter Linz Edition 4 Exercise 5.2 Question 11 (Page No. 145)
Is it possible for a regular grammar to be ambiguous?

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

by Naveen Kumar 3

105 views

0 votes

0 answers

107

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

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

by Naveen Kumar 3

339 views

0 votes

0 answers

108

Peter Linz Edition 4 Exercise 5.2 Question 9 (Page No. 145)
Show that a regular language cannot be inherently ambiguous.

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

by Naveen Kumar 3

127 views

0 votes

0 answers

109

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

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

by Naveen Kumar 3

112 views

0 votes

1 answer

110

Peter Linz Edition 4 Exercise 5.2 Question 7 (Page No. 145)
Construct an unambiguous grammar equivalent to the grammar in Exercise 6.

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

by Naveen Kumar 3

161 views

1 vote

1 answer

111

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

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

by Naveen Kumar 3

161 views

0 votes

1 answer

112

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

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

by Naveen Kumar 3

141 views

0 votes

0 answers

113

Peter Linz Edition 4 Exercise 5.2 Question 4 (Page No. 145)
Show that every s-grammar is unambiguous.

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

by Naveen Kumar 3

141 views

0 votes

1 answer

114

Peter Linz Edition 4 Exercise 5.2 Question 3 (Page No. 144)
Find an s-grammar for $L =$ {$a^nb^{n+1} : n ≥ 2$}.

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

by Naveen Kumar 3

199 views

0 votes

1 answer

115

Peter Linz Edition 4 Exercise 5.2 Question 2 (Page No. 144)
Find an s-grammar for $L =$ {$a^nb^n : n ≥ 1$}.

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

by Naveen Kumar 3

264 views

0 votes

1 answer

116

Peter Linz Edition 4 Exercise 5.2 Question 1 (Page No. 144)
Find an s-grammar for $L (aaa^*b + b)$.

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

by Naveen Kumar 3

221 views

0 votes

0 answers

117

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

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

by Naveen Kumar 3

199 views

0 votes

0 answers

118

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

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

by Naveen Kumar 3

83 views

0 votes

0 answers

119

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.

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

by Naveen Kumar 3

95 views

0 votes

0 answers

120

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

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

by Naveen Kumar 3

84 views

Page:

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

Recent questions tagged peter-linz-edition4