Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
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
498
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
368
views
peter-linz
peter-linz-edition4
context-free-grammar
context-free-language
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
284
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
186
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
145
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
522
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
365
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
205
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
ambiguous
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
328
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
ambiguous
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
398
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
parsing
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
279
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
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
330
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
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
275
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
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
214
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
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
148
views
peter-linz
peter-linz-edition4
theory-of-computation
inherently-ambiguous
grammar
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
151
views
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
ambiguous
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
401
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
regular-expression
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
180
views
peter-linz
peter-linz-edition4
theory-of-computation
inherently-ambiguous
grammar
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
167
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
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
225
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
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
219
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
ambiguous
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
197
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
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
203
views
peter-linz
peter-linz-edition4
theory-of-computation
ambiguous
grammar
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
364
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
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
456
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
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
374
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
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
258
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
137
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
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
155
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
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
137
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
Page:
« prev
1
2
3
4
5
6
7
8
9
...
13
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged peter-linz-edition4
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...