The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
1
answer
1
Context free grammar and push down automata.
Is true..? In an unambiguous grammar every string has exactly one derivation.
asked
Mar 21, 2018
in
Theory of Computation
by
hrcule

183
views
theoryofcomputation
contextfreegrammars
pushdownautomata
+1
vote
1
answer
2
Peter Linz Edition 4 Derivation Trees Definition 5.3 (Page No. 130)
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, 2018
in
Theory of Computation
by
tarun_svbk

156
views
theoryofcomputation
peterlinz
peterlinzedition4
contextfreegrammars
derivationtree
+2
votes
1
answer
3
regular grammers ambiguity
are grammars corresponding to DFA's unambiguous and those to NFA's are ambiguous? according to what I studied every DCFL is guaranteed has an unambiguous grammar though there are multiple grammars generating them every regular language is also DCFL hence ... follow the same but I doubt if every grammar corresponding to DFA is nonambiguous and that of NFA is ambiguous
asked
Jan 8, 2018
in
Compiler Design
by
Venkat Sai

145
views
theoryofcomputation
contextfreegrammars
+5
votes
1
answer
4
NIELT 2017 Question
Let G be a grammar in CFG and Let W1 and W2 is element of G such that w1 = w2 then which of the following is true? A. Any derivation of W1 has exactly the same number of steps as any derivation of W2 B. Different derivation have different length C.Some derivation of W1 may be shorter that derivation of W2 D. None of the options
asked
Dec 18, 2017
in
Theory of Computation
by
Durgesh Singh

1.2k
views
theoryofcomputation
isro2017
contextfreelanguages
contextfreegrammars
+3
votes
2
answers
5
ISRODEC201723
Identify the language generated by the following grammar $S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$ $\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b^n\mid n\geq m,m\geq0\}$ $\{a^m b^n\mid n> m,m>0\}$ $\{a^m b^m\mid n> m,m\geq0\}$
asked
Dec 17, 2017
in
Theory of Computation
by
gatecse

881
views
isrodec2017
theoryofcomputation
contextfreegrammars
0
votes
0
answers
6
Context free or not
How to understand such problems?
asked
Nov 20, 2017
in
Theory of Computation
by
Parshu gate

156
views
contextfreelanguages
identifyclasslanguage
contextfreegrammars
0
votes
0
answers
7
regular and context free
Let Σ = {a, b}. For a word w ∈ Σ* , let na(x) denote the number of a’s in w and let nb(x) denote the number of b’s in w. Consider the following language: L := {xy  x, y ∈ Σ* , na(x) = nb(y)} What can we say about L? (A) L is regular, but not contextfree. (B) L is contextfree, but not regular. (C) L is Σ*. (D) None of these.
asked
Nov 15, 2017
in
Theory of Computation
by
Parshu gate

46
views
contextfreegrammars
identifyclasslanguage
theoryofcomputation
0
votes
1
answer
8
#TOC Someone please Explain this Gate Question
This is the Gate Question  https://gateoverflow.in/3392/gate2008it78?show=155376#c155376 I couln't help but understand the balanced paranthesis thing, I know, () this is balanced, (( )) is balanced, ((( ))) is balanced, ... t have any intention to make a duplicate question/thread, I will close this question whenever I get my doubt solved. Thanks!
asked
Sep 26, 2017
in
Theory of Computation
by
iarnav

117
views
theoryofcomputation
contextfreelanguages
contextfreegrammars
cfg
0
votes
1
answer
9
#Parsing
Grammar : E>T+E/T T>id/id*T/(E) Is grammar LL(2)?
asked
Sep 26, 2017
in
Compiler Design
by
saxena0612

146
views
contextfreegrammars
0
votes
3
answers
10
UGCNETdec2009ii34
Contexfree Grammar (CFG) can be recognized by (A) Finite state automata (B) 2way linear bounded automata (C) push down automata (D) both (B) and (C)
asked
Sep 17, 2017
in
Theory of Computation
by
rishu_darkshadow

168
views
ugcnetdec2009ii
theoryofcomputation
contextfreegrammars
+1
vote
1
answer
11
context free grammers
L = {a^nb^m : n >= m+3} below context grammer is correct?? S ==> aA  Aa A ==> aAb  bAa  abA  baA  aa
asked
Jul 12, 2017
in
Theory of Computation
by
akhileshreddy

112
views
theoryofcomputation
cfg
contextfreegrammars
0
votes
1
answer
12
dr.O.G. kakde, context free grammar and syntax analysis
obtain regular grammar equivalent to the regular expression given below: 1) a*(ab)bb 2) (ab)*ba(ab)*
asked
Jun 28, 2017
in
Compiler Design
by
RAJKUMAR

146
views
contextfreegrammars
+1
vote
0
answers
13
UGCNETAUG2016III: 57
Let $G = (V, T, S, P)$ be a contextfree grammar such that every one of its productions is of the form $A \rightarrow ν$, with $ν = k > 1$. The derivation tree for any string $W \in L (G)$ has a height such that $h < \frac{(W1)}{k1}$ $\log_{k} W \leq h$ $\log_{k} W < h < \frac{(W1)}{k1}$ $\log_{k} W \leq h \leq \frac{(W1)}{k1}$
asked
Oct 5, 2016
in
Theory of Computation
by
makhdoom ghaya

246
views
ugcnetaug2016iii
theoryofcomputation
contextfreegrammars
+3
votes
2
answers
14
UGCNETJune2015III: 61
A context free grammar for $L=\{w \mid n_0 (w) > n_1 (w)\}$ is given by: $S \rightarrow 0 \mid 0S \mid 1 S S$ $S \rightarrow 0 S \mid 1 S \mid 0 S S \mid 1 S S \mid 0 \mid 1$ $S \rightarrow 0 \mid 0 S \mid 1 S S \mid S 1 S \mid S S 1$ $S \rightarrow 0 S \mid 1 S \mid 0 \mid 1$
asked
Aug 2, 2016
in
Theory of Computation
by
jothee

1.1k
views
ugcnetjune2015iii
theoryofcomputation
contextfreegrammars
+2
votes
2
answers
15
UGCNETDec2013II: 27
The context free grammar for the language: $L=\{a^n b^m \mid n \leq m + 3, n \geq 0, m \geq 0 \}$ is $S \rightarrow aaa \quad A; A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$ ... $S \rightarrow aaaA \mid aa \quad A \mid aA \mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$
asked
Jul 26, 2016
in
Theory of Computation
by
jothee

969
views
ugcnetdec2013ii
theoryofcomputation
contextfreegrammars
+1
vote
6
answers
16
UGCNETDec2014II: 35
The following ContextFree Grammar (CFG) : $S \rightarrow aB  bA$ $A \rightarrow a  as  bAA$ $B \rightarrow b  bs  aBB$ will generate Odd numbers of $a's$ and odd numbers of $b's$ Even numbers of $a's$ and even numbers of $b's$ Equal numbers of $a's$ and $b's$ Different numbers of $a's$ and $b's$
asked
Jul 23, 2016
in
Theory of Computation
by
makhdoom ghaya

715
views
ugcnetdec2014ii
theoryofcomputation
contextfreegrammars
+3
votes
1
answer
17
UGCNETJune2013III: 38
For every context free grammar (G) there exists an algorithm that passes any $w \in L(G)$ in number of steps proportional to $ln\mid w \mid$ $\mid w \mid$ $\mid w \mid^2$ $\mid w \mid^3$
asked
Jul 17, 2016
in
Theory of Computation
by
jothee

813
views
ugcnetjune2013iii
theoryofcomputation
contextfreegrammars
+9
votes
1
answer
18
ISI2013PCBCS4a
Give a contextfree grammar $G$ that generates $L = \{0^i1^j0^k \mid i + k = j\}$. Prove that $L = L(G)$.
asked
Jun 1, 2016
in
Theory of Computation
by
jothee

429
views
descriptive
isi2013pcbcs
contextfreegrammars
theoryofcomputation
Page:
« prev
1
2
3
4
5
6
7
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
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.2k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged contextfreegrammars
Recent Blog Comments
Can someone tell me how to check part B marks?...
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,497
answers
201,860
comments
95,316
users