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
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
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
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
Page:
« prev
1
2
3
4
5
6
7
8
...
13
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
From GATE to Australia
DRDO Previous Year Papers
From Rank 4200 to 64: My Journey to Success in GATE CSE Exam
What are the key things to focus on during the final 10-15 days before the GATE exam to improve performance?
All India GO Classes Mock test
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.6k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(649)
Exam Queries
(842)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(853)
Recent questions tagged peter-linz-edition4
Recent Blog Comments
Man, I feel you! I left my job to do gate this...
Yes, CDU provides assistance for internships...
Are you fully aware of the job opportunities in...
When this exam will happen ?
Can Someone guide me how to prepare for interview...