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
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
+1
vote
2
answers
1
UGCNETJune2019II78
Consider the following grammar: $S \rightarrow XY$ $X \rightarrow YaY \mid a \text{ and } Y \rightarrow bbX$ Which of the following statements is/are true about the above grammar? Strings produced by the grammar can have consecutive three $a$'s. Every string ... Every string produced by the grammar have $b$'s in multiple of $2$. a only n and c only d only c and d only
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
413k
points)

18
views
ugcnetjune2019ii
grammar
strings
0
votes
0
answers
2
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
(
317
points)

21
views
grammar
theoryofcomputation
0
votes
0
answers
3
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
(
14k
points)

19
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
4
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
(
14k
points)

29
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
5
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
(
14k
points)

16
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
6
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
(
14k
points)

13
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
7
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
(
14k
points)

17
views
peterlinz
theoryofcomputation
inherentlyambiguous
grammar
0
votes
0
answers
8
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
(
14k
points)

27
views
peterlinz
theoryofcomputation
grammar
regularexpressions
0
votes
0
answers
9
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
(
14k
points)

15
views
peterlinz
theoryofcomputation
inherentlyambiguous
grammar
0
votes
0
answers
10
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
(
14k
points)

11
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
11
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
(
14k
points)

16
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
12
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
(
14k
points)

13
views
peterlinz
theoryofcomputation
grammar
ambiguous
0
votes
0
answers
13
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
(
14k
points)

12
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
14
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
(
14k
points)

8
views
peterlinz
theoryofcomputation
ambiguous
grammar
0
votes
0
answers
15
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
(
14k
points)

15
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
16
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
(
14k
points)

16
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
17
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
(
14k
points)

10
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
18
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
(
14k
points)

27
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
19
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
(
14k
points)

14
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
20
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
(
14k
points)

11
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
21
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
(
14k
points)

21
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
22
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
(
14k
points)

26
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
23
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
(
14k
points)

13
views
peterlinz
theoryofcomputation
grammar
0
votes
1
answer
24
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
(
14k
points)

29
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
25
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
(
14k
points)

7
views
peterlinz
theoryofcomputation
grammar
+1
vote
3
answers
26
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
(
413k
points)

2.3k
views
gate2019
numericalanswers
compilerdesign
grammar
0
votes
1
answer
27
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
(
83
points)

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

185
views
compilerdesign
lrparser
parsing
grammar
0
votes
2
answers
29
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
(
11.4k
points)

143
views
gb2019mock1
grammar
0
votes
1
answer
30
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
(
11.4k
points)

125
views
gb2019mock1
grammar
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
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
Interview Experience at IITPalakkad
Follow @csegate
Recent questions tagged grammar
Recent Blog Comments
Hi, the previous email was sent to only those who...
@kriti05 can you please tell me when did you got...
It was said that there will be an address...
sir .I recvd a mail which states "Your...
49,808
questions
54,489
answers
188,270
comments
74,672
users