The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged grammar
0
votes
0
answers
1
Deletion of Useless Symbols from a Grammar Self Doubt
S → AB/a A → BC/b B → aB/C C → aC/B How do we remove useless symbols and productions from this grammar? While solving, i found that the useful symbols are {a,b,S,A} Hence, we must delete B,C But don’t know how to proceed
asked
Apr 30
in
Theory of Computation
by
Sukhbir Singh
(
329
points)

14
views
grammar
theoryofcomputation
0
votes
0
answers
2
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.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

19
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
3
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.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

27
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 5.2 Question 14 (Page No. 145)
Show that the grammar $S\rightarrow aSbSS\lambda$ is ambiguous, but that the language denoted by it is not.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

15
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
5
Peter Linz Edition 4 Exercise 5.2 Question 13 (Page No. 145)
Show that the following grammar is ambiguous. $S\rightarrow aSbSbSaS\lambda$
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

11
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
6
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.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

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

20
views
peterlinz
theoryofcomputation
grammar
regularexpressions
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 5.2 Question 9 (Page No. 145)
Show that a regular language cannot be inherently ambiguous.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

13
views
peterlinz
theoryofcomputation
inherentlyambiguous
grammar
0
votes
0
answers
9
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 abc.$
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

9
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 5.2 Question 7 (Page No. 145)
Construct an unambiguous grammar equivalent to the grammar in Exercise 6.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

16
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 5.2 Question 6 (Page No. 145)
Show that the following grammar is ambiguous. $S\rightarrow ABaaB,$ $A\rightarrow aAa,$ $B\rightarrow b.$
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

13
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 5.2 Question 5 (Page No. 145)
Let $G = (V, T, S, P)$ be an sgrammar. Give an expression for the maximum size of $P$ in terms of $V$ and $T$.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

11
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 5.2 Question 4 (Page No. 145)
Show that every sgrammar is unambiguous.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

8
views
peterlinz
theoryofcomputation
ambiguous
grammar
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 5.2 Question 3 (Page No. 144)
Find an sgrammar for $L =$ {$a^nb^{n+1} : n ≥ 2$}.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

14
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 5.2 Question 2 (Page No. 144)
Find an sgrammar for $L =$ {$a^nb^n : n ≥ 1$}.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

15
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 5.2 Question 1 (Page No. 144)
Find an sgrammar for $L (aaa^*b + b)$.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

9
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
17
Peter Linz Edition 4 Exercise 1.2 Question 23 (Page No. 30)
Show that the grammars $S \rightarrow aSbbSaSSa$ and $S \rightarrow aSbbSaa$ are not equivalent.
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

27
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
18
Peter Linz Edition 4 Exercise 1.2 Question 22 (Page No. 30)
Show that the grammar $G$ =({$S$}, {$a, b$}$, S, P$), with productions $S \rightarrow SSSSSaSbbSaλ$ , is equivalent to the grammar $S \rightarrow SS$ , $S \rightarrow λ$ , $S \rightarrow aSb$ , $S \rightarrow bSa$ .
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

13
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
19
Peter Linz Edition 4 Exercise 1.2 Question 21 (Page No. 29)
Are the two grammars with respective productions $S \rightarrow aSbabλ$, and $S \rightarrow aAbab$, $A \rightarrow aAbλ$, equivalent? Assume that $S$ is the start symbol in both cases.
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

11
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 1.2 Question 15 (Page No. 29)
Find grammars for the following languages on Σ = {a}. (a) L = {w : w mod 3 = 0}. (b) L = {w : w mod 3 > 0}. (c) L = {w : w mod 3 ≠ w mod 2}. (d) L = {w : w mod 3 ≥ w mod 2}.
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

19
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
21
Peter Linz Edition 4 Exercise 1.2 Question 14 (Page No. 28)
Let $Σ$ = {$a, b$}. For each of the following languages, find a grammar that generates it. (a) $L_1$ = {$a^nb^m : n ≥ 0, m > n$}. (b) $L_2$ = {$a^nb^{2n} : n ≥ 0$}. (c) $L_3$ = {$a^{n+2}b^n : n ≥ 1$}. (d) $L_4$ = {$a^nb^{n−3} : n ≥ 3$}. (e) $L_1 L_2$. (f) $L_1 ∪ L_2$. (g) $L_1^3$. (h) $L_1^*$. (i) $L_1\bar{L}_4$.
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

23
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
22
Peter Linz Edition 4 Exercise 1.2 Question 13 (Page No. 28)
What language does the grammar with these productions generate? $S \rightarrow Aa$ , $A \rightarrow B$ , $B \rightarrow Aa$ .
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

12
views
peterlinz
theoryofcomputation
grammar
0
votes
1
answer
23
Peter Linz Edition 4 Exercise 1.2 Question 12 (Page No. 28)
Give a simple description of the language generated by the grammar with productions $S \rightarrow aA,$ $A \rightarrow bS,$ $S \rightarrow λ.$
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

25
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 1.2 Question 11 (Page No. 28)
Find grammars for $Σ$ = {$a, b$} that generate the sets of (a) all strings with exactly one $a$. (b) all strings with at least one $a$. (c) all strings with no more than three $a$’s. (d) all strings with at least three $a$’s. In each case, give convincing arguments that the grammar you give does indeed generate the indicated language.
asked
Mar 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.2k
points)

7
views
peterlinz
theoryofcomputation
grammar
+1
vote
3
answers
25
GATE201943
Consider the augmented grammar given below: $S’ \rightarrow S$ $S \rightarrow \langle L \rangle \mid id$ $L \rightarrow L, S \mid S$ Let $I_0 = \text{CLOSURE} (\{[S’ \rightarrow \cdot S ]\}).$ The number of items in the set $\text{GOTO} (I_0, \langle \: )$ is______
asked
Feb 7
in
Compiler Design
by
Arjun
Veteran
(
400k
points)

2.2k
views
gate2019
numericalanswers
compilerdesign
grammar
0
votes
1
answer
26
Formal Languages
Consider the language defined as L = { $a^pb^qa^r$  p = q or q = r} . L complement is Regular CFL but not regular CSL but not CSL DCFL
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
159
points)

37
views
theoryofcomputation
grammar
0
votes
3
answers
27
clr(1) parser
grammar is CLR(1) or not? if yes then how?
asked
Jan 21
in
Compiler Design
by
Rahul_Rathod_
Junior
(
561
points)

154
views
compilerdesign
lrparser
parsing
grammar
0
votes
2
answers
28
GATEBOOK2019 Mock Test133
Consider the CFG grammar $G = (N={S, A, B}, T=\{a,b\}, P, S)$ where the set of productions $P$ is given below: S → A a A b  B b B a A → a  ε B → b  ε Which of the following statements is FALSE ... for parsing using a predictive (backtrackfree) algorithm FOLLOW of any nonterminal that derive the empty string does not conflict with its FIRST set All of the above
asked
Jan 19
in
Compiler Design
by
GATEBOOK
Boss
(
17.3k
points)

143
views
gb2019mock1
grammar
0
votes
1
answer
29
GATEBOOK2019 Mock Test162
Consider these three grammars. $\begin{array} \text{Grammar} & G1: \\ E & \rightarrow & E & + & T & \mid & T \\ T & \rightarrow & T & * & v & \mid & v \end{array}$ ... generated by $G_3,$ then it can be generated by $G_1.$ If $w$ can be generated by $G_2,$ then it can be generated by $G_1.$
asked
Jan 19
in
Compiler Design
by
GATEBOOK
Boss
(
17.3k
points)

125
views
gb2019mock1
grammar
0
votes
0
answers
30
MadeEasy Test Series 2019: Theory of computation  Grammer
Let L be the language of all strings on [0,1] ending with 1. Let X be the language generated by the grammar G. $S \rightarrow 0S/1A/ \epsilon $ $A \rightarrow 1S/0A$ Then $L \cup X= $ ∅ ∑* L X Ans given : B. ... a language which contains all strings that do not end with 1. But is it so? Can't we generate 11 from the grammar? Please verify.
asked
Jan 15
in
Theory of Computation
by
MiNiPanda
Boss
(
22k
points)

91
views
theoryofcomputation
grammar
madeeasytestseries2019
madeeasytestseries
Page:
1
2
3
4
5
6
...
11
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
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has begun
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
Follow @csegate
Recent questions tagged grammar
Recent Blog Comments
@Anuj Mishra how did you study CLRS?what...
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
49,430
questions
53,616
answers
185,966
comments
70,892
users