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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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
1
answer
1
Grammars
Please provide example to disapprove the following points: 1.every DCFG need not be a LR(K). 2.every DCFG need not be a LL(K). 3.every DCFL is not LL(k).
asked
Jul 22
in
Compiler Design
by
junaid ahmad
Loyal
(
9k
points)

44
views
compilerdesign
grammar
0
votes
2
answers
2
Languages
Consider a language over Σ={a,b} the description of L is given below. L={ PQ  P ∈(a,b)* , Q ∈ (a,b)* and na(P) = nb(Q) }. Select the correct option. 1. L is DCFL but not regular. 2. L is CSL but not CFL. 3. L is CFL but not DCFL. 4. None of these.
asked
Jul 3
in
Theory of Computation
by
Priyansh Singh
(
49
points)

91
views
theoryofcomputation
regularlanguages
contextfreelanguage
grammar
+2
votes
1
answer
3
Introduction to Formal Language, Fall 2017
asked
Jun 30
in
Theory of Computation
by
Apoorva Jain
(
63
points)

58
views
theoryofcomputation
regularlanguages
peterlinz
finiteautomata
grammar
0
votes
1
answer
4
Grammer
A grammar will be meaningless of the (a) terminal set and nonterminal set are not disjoint (b) left hand side of a productions is a single terminal (c) left hand side of a production has no nonterminal (d) all of the above
asked
Jun 25
in
Theory of Computation
by
K ANKITH KUMAR
(
141
points)

54
views
theoryofcomputation
grammar
0
votes
0
answers
5
UGC NET DEC 2017 PAPER 2 Q 34
Which of the following statements is/are TRUE ? (i) The grammar S → SS  a is ambiguous (where S is the start symbol). (ii) The grammar S → 0S1  01S  e is ambiguous (the special symbol e represents the empty string and S is the start symbol). (iii) The grammar ... TRUE (D) All of (i), (ii) and (iii) are TRUE Sure shot (i) and (ii) are true i want third one in brief
asked
Jun 19
in
Compiler Design
by
Nikhil Patil
(
479
points)

111
views
compilerdesign
grammar
ambiguous
+1
vote
2
answers
6
Gradup topicwise question doubt
Identify the language generated by the following grammar: $S>AB$ $A>aAb\epsilon$ $B>bBb$ (A)$\{a^m b^nn≥m, m>0\}$ (B)$\{a^m b^nn≥m, m≥0\}$ (C)$\{a^m b^nn>m, m>0\}$ (D)$\{a^m b^nn>m, m≥0\}$ I select option C but it is wrong, correct answer is option D. I could not understand Gradup answer explanation.Please help me to rectify my fault.
asked
May 24
in
Theory of Computation
by
Sona Barman
Active
(
1.2k
points)

68
views
theoryofcomputation
language
of
grammar
0
votes
4
answers
7
Context Free Language
L= { $a^{n}b^{m}$  $n<=m<=2n$ } a) DCFL b) CFL but not DCFL c) Not CFL
asked
May 6
in
Theory of Computation
by
Subham Nagar
Junior
(
649
points)

141
views
contextfreelanguage
theoryofcomputation
grammar
0
votes
1
answer
8
Attribute Grammar
Can someone explain these terms clearly these terms with examples? Attribute Grammar Synthesized attributes Inherited attributes L and S Attributes
asked
Apr 5
in
Compiler Design
by
smsubham
Loyal
(
6.8k
points)

45
views
compilerdesign
grammar
0
votes
1
answer
9
LL(n)
LL(1) parser cannot accept nondeterministic grammar at we have only single lookahead and there can be no predictable parsing in this case. Suppose we have LL(n) and we are given that maximum length of nondeterminism in a production is n  1. Can we use this grammar for LL(n) predictive parsing?
asked
Apr 4
in
Compiler Design
by
smsubham
Loyal
(
6.8k
points)

94
views
compilerdesign
ll1
parsing
lrparser
grammar
0
votes
3
answers
10
LR(0) Parsing Table
Please anyone create a $LR(0)$ Parsing table on this grammar and show the working of each step: $S' \rightarrow S$ $S \rightarrow S$;$A \mid A$ $A \rightarrow E \mid id := E$ $E \rightarrow E+id \mid id$ NonTerminals: $S'$ $S$ $A$ $E$ Terminals$: ; := + id$ Please take a screenshot of copy and show in the answer the whole working.
asked
Mar 18
in
Compiler Design
by
rahuldb
Junior
(
667
points)

192
views
compilerdesign
lrparser
parsing
grammar
+1
vote
3
answers
11
Find the grammar for the languages (PeterLinz)
asked
Feb 27
in
Theory of Computation
by
Mk Utkarsh
Boss
(
14.1k
points)

131
views
theoryofcomputation
peterlinz
grammar
+1
vote
1
answer
12
Exercise 1.2
Find the grammar for the following language $L = \left \{ w: \left  w \right  mod 3 \geq \left  w \right  mod 2 \right \}$
asked
Feb 26
in
Theory of Computation
by
Mk Utkarsh
Boss
(
14.1k
points)

95
views
theoryofcomputation
grammar
peterlinz
+2
votes
1
answer
13
PeterLinz (Exercise 1.2)
$L = \left \{ a^{n} b^{m} : n\geq 0,m>n \right \}$ Find a grammar that generates L3
asked
Feb 26
in
Theory of Computation
by
Mk Utkarsh
Boss
(
14.1k
points)

124
views
theoryofcomputation
peterlinz
grammar
+1
vote
1
answer
14
Derivation Trees, Peter Linz
Which of the following is false for derivation tree of CFG $G (V, T, P, S)$ ? The root is labeled $S$. Every leaf has a label from $V ⋃ T ⋃ \{ λ \}$. A vertex with a child labeled $λ$ can only have it as the rightmost child. $\text{1 & 3}$ $\text{1 & 2}$ $\text{2 & 3}$ $\text{Only 2}$
asked
Feb 24
in
Theory of Computation
by
tarun_svbk
Active
(
1.5k
points)

60
views
theoryofcomputation
peterlinz
grammar
derivationtree
0
votes
2
answers
15
Simple Grammar
Consider Grammar G with the following characteristic $A → ax$, where $A ∈ V$, $a ∈ T$, $x ∈ V^*$, and any pair $( A, a )$ occurs at most once in $P$. For example, $S → aA \mid aB...,$ is not a grammar of type $G$ because the pair $(S,a)$ occur in two productions. ... string w belonging to $L(G)$ ? $\mid w \mid^3$ $\mid w \mid$ $2^{\mid w \mid}$ Not a function of $\mid w \mid$ alone.
asked
Feb 24
in
Theory of Computation
by
tarun_svbk
Active
(
1.5k
points)

60
views
theoryofcomputation
contextfreelanguage
peterlinz
grammar
cfg
0
votes
0
answers
16
Sentential forms
Restricting only to the leftmost derivations, how many sentential forms can exhaustive search parsing generate ? $O(P^{\mid w \mid})$ $O(P^{\mid w \mid +1})$ $O(P^{2\mid w \mid})$ $O(P^{2\mid w \mid + 1})$ where, $P$ is the number of productions and w is the word to be generated.
asked
Feb 24
in
Theory of Computation
by
tarun_svbk
Active
(
1.5k
points)

39
views
theoryofcomputation
contextfreelanguage
peterlinz
grammar
0
votes
0
answers
17
IA Languages
Consider the language $L = \{a^nb^nc^m\}U \{a^nb^mc^m\}$ with $n$ and $m$ nonnegative. Which of the following options is correct? There is no context free grammar possible for $L$. There exists a simple grammar for $L$. There exists an unambiguous grammar for $L$. There exists an ambiguous grammar for $L$.
asked
Feb 24
in
Theory of Computation
by
tarun_svbk
Active
(
1.5k
points)

50
views
theoryofcomputation
contextfreelanguage
peterlinz
grammar
0
votes
1
answer
18
Grammer
Can I give any grammer for the language L = { anbncn / n>=1} Like this
asked
Feb 1
in
Theory of Computation
by
MRINMOY_HALDER
(
109
points)

70
views
theoryofcomputation
grammar
+1
vote
1
answer
19
VirtualGate2018I19
Consider the grammar given S>AA A>aA / b How many entries will be blank in the GOTO table for SR(0) items? What is the meaning of SR(0) items?
asked
Jan 25
in
Compiler Design
by
Avdhesh Singh Rana
Active
(
3.2k
points)

72
views
parsing
grammar
+2
votes
1
answer
20
Identify the grammar
S $\rightarrow A$ A $\rightarrow AB/$$\epsilon$ B $\rightarrow aB/b$ is this grammar LALR(1) ?
asked
Jan 19
in
Compiler Design
by
Mk Utkarsh
Boss
(
14.1k
points)

79
views
grammar
parsing
+2
votes
2
answers
21
Grammar LL(1) LR(0)
S> ABd A>aAb B>bBc Is the above grammar both LL(1) and LR(0)?
asked
Jan 18
in
Compiler Design
by
Tuhin Dutta
Loyal
(
7.9k
points)

214
views
compilerdesign
lrparser
ll1
grammar
+2
votes
1
answer
22
Context Free Language
Is B context free? Please explain in detail.
asked
Jan 6
in
Theory of Computation
by
Shubham Kumar Gupta
Junior
(
547
points)

190
views
contextfreelanguage
theoryofcomputation
identifyclasslanguage
regularlanguages
grammar
+1
vote
0
answers
23
LL(k) Grammar
Consider the grammar with the following productions. S→aaB/aaC B→b C→c Which of the following option is true ? (A) The grammar is LL(3) (B) The grammar is LL(1) (C) The grammar is LL(2) (D) It can’t be LL(k) grammar for any k, as it contains left factoring.
asked
Dec 31, 2017
in
Compiler Design
by
ankitgupta.1729
Loyal
(
6.6k
points)

244
views
compilerdesign
grammar
ll1
parsing
+1
vote
1
answer
24
DCFG grammar
Can a DCFG grammar be Ambiguous? If so please provide an example.
asked
Dec 24, 2017
in
Theory of Computation
by
VS
Loyal
(
8.9k
points)

191
views
theoryofcomputation
grammar
+1
vote
0
answers
25
LL(k)
I know that LL(1) grammar can have No left factoring ,No Left recursion and No Ambiguity. Is same thing true for LL(k) as well i.e. LL(k) which is reading k symbols at a time from input string. Does LL(k) grammar can have No left factoring ,No Left recursion and No Ambiguity ?
asked
Dec 24, 2017
in
Compiler Design
by
VS
Loyal
(
8.9k
points)

361
views
compilerdesign
grammar
0
votes
3
answers
26
Type of grammar
Why isn't it LL(1) ?
asked
Dec 5, 2017
in
Compiler Design
by
Parshu gate
Active
(
4.9k
points)

196
views
parsing
compilerdesign
grammar
ll1
lrparser
0
votes
1
answer
27
Grammars
HI Mates, Is it true or false..? If yes or no please explain..? Every Regular set has a LR(1) Grammar....?
asked
Nov 30, 2017
in
Theory of Computation
by
Sahil1994
Junior
(
971
points)

42
views
theoryofcomputation
grammar
0
votes
0
answers
28
General syllabus doubt
Hello, The gate 2018 syllabus explicitly mentions regular languages, context free languages and turing machines. It does not say anything about context sensitive languages and linear bounded automata..How much of these topics should i study?..definitions? closure properties?
asked
Nov 23, 2017
in
Study Resources
by
Tridhara Chakrabarti
(
255
points)

91
views
contextsensitive
theoryofcomputation
syllabus
gate2018preparation
grammar
+1
vote
0
answers
29
TOC: Chomsky hierarchy
Where does NP hard / NP complete problems fits in the Chomsky hierarchy ? Is there any relation of Np hard problems with RE languages?
asked
Nov 21, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
24.5k
points)

73
views
theoryofcomputation
grammar
+1
vote
1
answer
30
Gate Sample 2018
L1 = {canbn} ∪ {danb2n} L2 = {anbnc} ∪ {anb2nd} (a) Both are DCFL’s (b) Both are NCFL’s (c) L1 is DCFL, L2 is NCFL (d) L1 is NCFL, L2 is DCFL Solution: Option (c) i know answer but need proper solution for understanding please explain elaborately....
asked
Nov 17, 2017
in
Theory of Computation
by
Pranav Madhani
Junior
(
905
points)

103
views
gate2018
question
sample
grammar
regular
contect
contextfreelanguages
Page:
1
2
3
4
5
6
...
8
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
Anxiety
Nielit 2018
Donation (Kerala Flood)
Schedule for GATE 2019
GATE 2019 official website
Follow @csegate
Gatecse
Recent questions tagged grammar
Recent Blog Comments
Thanx Mk utkarsh and nikhil bro ... i really ...
Firstly I am not topper. or ranker.
but ...
If you are not able to understand the concept of ...
done:)
Thanx man ... i really appreciate it ...
38,203
questions
45,703
answers
132,820
comments
49,755
users