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
+1
vote
1
answer
1
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
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

10
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
2
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
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

8
views
peterlinz
theoryofcomputation
grammar
+1
vote
1
answer
3
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
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

5
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
4
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
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

5
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
5
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
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

2
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
6
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
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

2
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
7
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
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

3
views
peterlinz
theoryofcomputation
grammar
0
votes
0
answers
8
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
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

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

2.1k
views
gate2019
numericalanswers
compilerdesign
grammar
0
votes
1
answer
10
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
(
149
points)

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

71
views
compilerdesign
lrparser
parsing
grammar
0
votes
2
answers
12
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
(
15.3k
points)

125
views
gb2019mock1
grammar
0
votes
1
answer
13
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
(
15.3k
points)

113
views
gb2019mock1
grammar
0
votes
0
answers
14
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
(
21.1k
points)

76
views
theoryofcomputation
grammar
madeeasytestseries2019
madeeasytestseries
0
votes
1
answer
15
#compiler
asked
Jan 9
in
Compiler Design
by
amit166
Junior
(
713
points)

33
views
grammar
0
votes
0
answers
16
Zeal Test Series 2019: Theory of Computation  Grammar
Consider the following statements. S1: An unambiguous left recursive grammar must be CLR(1). S2: A DCFG may or may not be LL(1). Select the correct option: 1.Both S1 and S2 are true. 2.Both S1 and S2 are false. 3. S1 is false and S2 is true. 4.S1 is true and S2 is false. According to me S1 false and S2 true but answer given 1
asked
Jan 2
in
Theory of Computation
by
Prince Sindhiya
Loyal
(
6.2k
points)

54
views
zeal
theoryofcomputation
grammar
zeal2019
+1
vote
0
answers
17
NonLeft recursive grammar of the below grammar.
Grammar. S → Aa  B A → Ac  Aad  bd  epsilon . .
asked
Jan 2
in
Compiler Design
by
susgir2
Active
(
1.4k
points)

48
views
compilerdesign
leftrecursion
grammar
parsing
recurrence
+1
vote
0
answers
18
MadeEasy Test Series: Compiler Design  Grammar
Consider the following grammar G shown Below : S → abS  ScS  d  c The number of terminals in follow set of nonterminal S is ___________________ Is “$” symbol considered terminal?
asked
Dec 30, 2018
in
Compiler Design
by
vinay chauhan
Junior
(
811
points)

74
views
first
follow
madeeasytestseries
grammar
0
votes
0
answers
19
context free grammer
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?
asked
Dec 24, 2018
in
Theory of Computation
by
Rahul_Rathod_
Junior
(
565
points)

55
views
grammar
contextfreelanguage
dcfl
cfg
0
votes
2
answers
20
MadeEasy Test Series: Theory Of Computation  Grammar
i thought that it is the language where both start and end symbols are same and i got 65 but the ans is 29
asked
Dec 22, 2018
in
Theory of Computation
by
suneetha
Junior
(
549
points)

60
views
madeeasytestseries
theoryofcomputation
grammar
0
votes
1
answer
21
MadeEasy Test Series: Theory Of Computation  Grammar
what is the answer
asked
Dec 22, 2018
in
Theory of Computation
by
suneetha
Junior
(
549
points)

50
views
madeeasytestseries
theoryofcomputation
grammar
0
votes
1
answer
22
MadeEasy Test Series: Theory Of Computation  Grammar
G1: S→ aSa bSbe G2:S→ aaSbbS e the shortest length strings which does not belongs to L(g1) but belongs to L(G2) is
asked
Dec 22, 2018
in
Theory of Computation
by
suneetha
Junior
(
549
points)

77
views
madeeasytestseries
theoryofcomputation
grammar
+1
vote
0
answers
23
PARSER
An $\epsilon$ free LL(1) grammar is also a SLR(1) and hence LALR(1) and LR(1) too. Is this statement true ?
asked
Dec 20, 2018
in
Compiler Design
by
junaid ahmad
Loyal
(
9.4k
points)

43
views
compilerdesign
parsing
grammar
0
votes
0
answers
24
Self doubt
I know that for a recursively enumerable language there exists an unrestricted grammar and we have formally defined unrestricted grammar. I want to know whether for every recursive language, there is a grammar or not, and if there is, is there a formal definition of the same?
asked
Dec 20, 2018
in
Theory of Computation
by
subho16
(
169
points)

47
views
theoryofcomputation
turingmachine
grammar
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
25
Does operator grammar belong to both NCFL and DCFL?
Operator precedence parser even parses ambiguous grammars that are in form of operator grammars. I am inquiring about the nature of the ambiguous grammar. Could the language described by the operator grammar be both $DCFL$ or $NCFL$?
asked
Dec 9, 2018
in
Compiler Design
by
2019_Aspirant
Active
(
1.6k
points)

39
views
compilerdesign
grammar
0
votes
0
answers
26
Grammer
Which of the following problem is undecidable? A) membership problem for CFL B) membership problem for regular language C)membership problem for csl D)membership problem for type O language
asked
Dec 8, 2018
in
Theory of Computation
by
Shivshankar
(
41
points)

46
views
theoryofcomputation
grammar
0
votes
0
answers
27
#gate #1997
A language L is a subset of Pascal with the following constructs: a). Expressions involving the operators ‘+’ and ‘<‘ only b). Assignment statements c). ‘while’ statements and d). Compound statements with the syntax ‘begin…………..end’ Give an unambiguous grammar for L.
asked
Dec 4, 2018
in
Compiler Design
by
Gangani_Son
(
163
points)

22
views
usergate1997
usermod
grammar
0
votes
0
answers
28
parser doubt
Consider the statements: (i) Every regular grammar is LL(1) (ii) Every LL(1) grammar is LALR(1) (iii) All LR(0) grammars are LL(k) (iv) A contextfree grammar without left factoring and left recursion can be ambiguous Which of the above statement/s is/are TRUE? (i) only (i) and (iii) only (ii) and (iv) only (iv) only
asked
Dec 1, 2018
in
Compiler Design
by
Pavan Shetty
(
87
points)

45
views
compilerdesign
parsing
grammar
0
votes
0
answers
29
TOC  PDA
Consider a push down automata (PDA) below which runs over the input alphabet (a, b). It has the stack alphabet {z0, X}, where z0 is the bottom of stack marker. The set of states of PDA is {q0,q1} where q0 is the start state and rules of the PDA are, (The languare accepted by the grammar is)
asked
Nov 30, 2018
in
Theory of Computation
by
rahuljai
(
437
points)

67
views
pushdownautomata
theoryofcomputation
contextfreelanguage
grammar
cfg
0
votes
0
answers
30
MadeEasy Test Series: Compiler Design  Grammar
X' >.X ,$ X>.X+Y ,$/+ X>.Y ,$/+ Y>.Y*Z ,$/+/* Y>.Z ,$/+/* Z>.(X) ,$/+/* Z>.id ,$/+/*
asked
Nov 23, 2018
in
Compiler Design
by
jatin khachane 1
Loyal
(
6.4k
points)

86
views
madeeasytestseries
compilerdesign
grammar
Page:
1
2
3
4
5
6
...
10
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 Gandhinagar review
Is DAIICT good for doing MTech ?
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
Follow @csegate
Recent questions tagged grammar
Recent Blog Comments
congrats man!!! u surely need guts to leave job...
You won't get M.Tech degree then
I have generic query , not just about iit gn but...
Thank you Abhishek
Heartliest Congratulation Abhishek Bhai. This was...
48,515
questions
52,763
answers
183,377
comments
68,234
users