The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged contextfreegrammars
0
votes
0
answers
1
Peter Linz Edition 4 Exercise 6.2 Question 10 (Page No. 170)
Convert the grammar $S\rightarrow aSbbSaab$ into Greibach normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

28
views
peterlinz
theoryofcomputation
contextfreegrammars
gnf
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 6.2 Question 9 (Page No. 170)
Show that for every contextfree 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$.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

17
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
3
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)$.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

25
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 6.2 Question 7 (Page No. 169)
Draw the dependency graph for the grammar in Exercise 4.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

16
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
5
Peter Linz Edition 4 Exercise 6.2 Question 6 (Page No. 169)
Let $G = (V, T, S, P)$ be any contextfree grammar without any $λ$productions or unitproductions. 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 $(k1)P+T$ production rules.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

26
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 6.2 Question 5 (Page No. 169)
Convert the grammar with productions $S\rightarrow ABaB,$ $A\rightarrow aab\lambda,$ $B\rightarrow bbA$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

22
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
7
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 BAaA\lambda$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

8
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 6.2 Question 3 (Page No. 169)
Transform the grammar $S\rightarrow aSaAA, A\rightarrow abAb$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

16
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 6.2 Question 2 (Page No. 169)
Convert the grammar $S\rightarrow aSbab$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

24
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
10
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 contextfree 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.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

19
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
11
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_1Ax_2A...x_nA,$ and, $A\rightarrow y_1y_2...y_m,$ where $A$ is not a ... $Z\rightarrow x_iZx_i,$ $i=1,2,3, ,n.$ is equivalent to the original grammar.
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
12
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 AaaBc\lambda,$ $B\rightarrow Bbbc$ so that it no longer has productions of the form $A → Ax$ or $B → Bx.$
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

15
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 6.1 Question 23 (Page No. 163)
Prove the following result. Let $G = (V, T, S, P )$ be a contextfree grammar. Divide the set of productions whose left sides are some given variable (say, $A$), into two disjoint subsets $A\rightarrow Ax_1Ax_2...Ax_n,$ $A\rightarrow y_1y_2...y_m,$ ... $Z\rightarrow x_ix_iZ,$ $i=1,2,3, ,n.$ Then $L (G) = L ( \widehat G).$
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 6.1 Question 22 (Page No. 163)
A contextfree 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.
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

16
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
15
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 unitproductions?
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

7
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
16
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.
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

8
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 6.1 Question 19 (Page No. 163)
Suppose that a contextfree 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.
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

18
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
18
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.
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

20
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 6.1 Question 17 (Page No. 162)
Show that if a grammar has no $λ$productions and no unitproductions, 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.
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

21
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 6.1 Question 16 (Page No. 162)
Let $G$ be a grammar without $λ$productions, but possibly with some unitproductions. 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$.
asked
Apr 17
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

22
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 6.1 Question 14 (Page No. 162)
Suppose that $G$ is a contextfree 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) –$ {$λ$}.
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

26
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
1
answer
22
Peter Linz Edition 4 Exercise 6.1 Question 12 (Page No. 162)
Remove $λ$productions from the grammar with productions $S\rightarrow aSbSS\lambda.$ What language does the resulting grammar generate?
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

44
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
23
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 contextfree grammar without $λ$productions. Then there exists a contextfree grammar $\widehat{G}=(\widehat{V},\widehat{T},S,\widehat{P})$ that does not have any unitproductions and that is equivalent to $G$.
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

20
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
24
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 contextfree grammar with $λ$ not in $L (G)$. Then there exists an equivalent grammar $\widehat{G}$ having no $λ$productions.
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

26
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
1
answer
25
Peter Linz Edition 4 Exercise 6.1 Question 8 (Page No. 162)
Remove all unitproductions, all useless productions, and all λproductions from the grammar $S\rightarrow aAaBB,$ $A\rightarrow aaA\lambda,$ $B\rightarrow bBbbC,$ $C\rightarrow B.$ What language does this grammar generate?
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

46
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
+1
vote
0
answers
26
Peter Linz Edition 4 Exercise 6.1 Question 7 (Page No. 162)
Eliminate all λproductions from $S\rightarrow AaBaaB,$ $A\rightarrow \lambda,$ $B\rightarrow bbA\lambda.$
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

24
views
peterlinz
theoryofcomputation
contextfreegrammars
+1
vote
1
answer
27
Peter Linz Edition 4 Exercise 6.1 Question 6 (Page No. 161)
Eliminate useless productions from $S\rightarrow aaABC,$ $A\rightarrow aB\lambda,$ $B\rightarrow Aa,$ $C\rightarrow cCD,$ $D\rightarrow ddd.$
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

33
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 6.1 Question 5 (Page No. 161)
Eliminate all useless productions from the grammar $S\rightarrow aSAB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

28
views
peterlinz
contextfreegrammars
contextfreelanguage
0
votes
0
answers
29
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?
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

24
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 6.1 Question 3 (Page No. 161)
Show that the two grammars $S\rightarrow abABba,$ $A\rightarrow aaa,$ $B\rightarrow aAbb$ and $S\rightarrow abAaAabAbbba,$ $A\rightarrow aaa$ are equivalent.
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

24
views
peterlinz
theoryofcomputation
contextfreegrammars
Page:
« prev
1
2
3
4
5
6
7
next »
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged contextfreegrammars
Recent Blog Comments
Really helpful sir Thanks a ton👍👍
Amazing work Sir
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
50,644
questions
56,516
answers
195,578
comments
101,129
users