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
Recent questions tagged cfg
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 4 Question 15 (Page No. 212)
Show that the problem of determining whether a CFG generates all strings in $1^{\ast}$ is decidable. In other words, show that $\{\langle { G \rangle} \mid \text{G is a CFG over {0,1} and } 1^{\ast} \subseteq L(G) \}$ is a decidable language.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.5k
points)

13
views
michaelsipser
theoryofcomputation
cfg
decidability
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 4 Question 14 (Page No. 211)
Let $\Sigma = \{0,1\}$. Show that the problem of determining whether a $CFG$ generates some string in $1^{\ast}$ is decidable. In other words, show that $\{\langle {G \rangle}\mid \text{G is a CFG over {0,1} and } 1^{\ast} \cap L(G) \neq \phi \}$ is a decidable language.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.5k
points)

5
views
michaelsipser
theoryofcomputation
cfg
decidability
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 4 Question 4 (Page No. 211)
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
asked
Oct 16, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.5k
points)

16
views
michaelsipser
theoryofcomputation
turingmachine
cfg
decidability
proof
0
votes
1
answer
4
ACE Academy: Recognition of CFG
$L1 =\left \{ a^{m} b^{n} c^{p}  \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p}  \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$ $(a)$ Both are NCFL’s $(b)$ L1 is DCFL and L2 is NCFL $(c)$ L1 is NCFL and L2 is not contextfree $(d)$ Both are not contextfree
asked
May 23, 2019
in
Theory of Computation
by
Hirak
Active
(
3.6k
points)

91
views
cfg
contextfreelanguages
dcfl
+1
vote
1
answer
5
Ace Test Series: Compiler Design  Left Recursion Elimination
asked
Jan 23, 2019
in
Compiler Design
by
Shankar Kakde
(
195
points)

88
views
acetestseries
compilerdesign
cfg
leftrecursion
0
votes
0
answers
6
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_
(
431
points)

76
views
grammar
contextfreelanguages
dcfl
cfg
0
votes
0
answers
7
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
Junior
(
551
points)

134
views
pushdownautomata
theoryofcomputation
contextfreelanguages
grammar
cfg
0
votes
0
answers
8
Context Free Grammar
Consider the following CFG 'G' S> aA/bSS/SS A> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked
Oct 18, 2018
in
Theory of Computation
by
Sambhrant Maurya
Active
(
3.9k
points)

69
views
theoryofcomputation
contextfreegrammars
contextfreelanguages
cfg
pushdownautomata
0
votes
0
answers
9
doubt
L1 = { a^n b^n c^m  n,m>=0} L2 = { a^m b^n c^n  m,n>=0} L1 intersection L2 = { { a^n b^n c^n  n>=0} how we do intersection plz explain using grammer....
asked
Oct 1, 2018
in
Theory of Computation
by
bhavnakumrawat5
(
169
points)

27
views
cfg
–2
votes
0
answers
10
boook
L={an . bn . cm . cn  m,n ≥ 0 } find CFG of corresponding Language
asked
Sep 19, 2018
in
Theory of Computation
by
amit166
Junior
(
775
points)

29
views
cfg
+1
vote
2
answers
11
#Test series
Consider the following CFG. S → aSa  bSb  a  b  ε For the above CFG, the total number of strings generated whose length is less than or equal to 8 [exclude the empty string] is _____________.
asked
Jul 31, 2018
in
Theory of Computation
by
himgta
Active
(
3.7k
points)

65
views
cfg
0
votes
1
answer
12
#Self doubt
L = {x^a y^a : a ≥ 1} I. L^3 is context free. II. ⌈√ L⌉ is not context free. Which of the following is correct? (a) I only (b) II only (c) Both I and II (d) None of the above
asked
Jul 30, 2018
in
Theory of Computation
by
himgta
Active
(
3.7k
points)

38
views
cfg
+1
vote
1
answer
13
#Self doubt
Whether a given contextfree language is regular is decidable or undecidable? Prove your answer!
asked
Jul 29, 2018
in
Theory of Computation
by
himgta
Active
(
3.7k
points)

71
views
decidability
cfg
+3
votes
1
answer
14
give cfg for the language
Let $L=\{w \mid w \in (0+1)^+ , N_0(w) \le N_1(w) \le 2N_0(w) \}$,where $N_i(w)$ represents number of $i's$ in string $w$. a) Give a CFG for $L$ b) is Lc = Σ* L context  free? c) Let $\frac{1}{2}$L = $\{x  ∃y ∈ L , x = y , x.y ∈ L \}$.is $\frac{1}{2}$L contextfree?
asked
Apr 30, 2018
in
Theory of Computation
by
Sambit Kumar
Active
(
4.2k
points)

239
views
cfg
theoryofcomputation
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, 2018
in
Theory of Computation
by
tarun_svbk
Active
(
1.7k
points)

212
views
theoryofcomputation
contextfreelanguages
peterlinz
grammar
cfg
+1
vote
0
answers
16
Self doubt
Is equivalence problem decidable in case of: 1) CFG's 2) DCFG's If yes, then how?
asked
Jan 19, 2018
in
Theory of Computation
by
Aakanchha
Junior
(
655
points)

49
views
cfg
theoryofcomputation
+2
votes
0
answers
17
Kindly clear few queries regarding Automata theory !
I'm studying through Linz and Have few confusions : Let $\sum = {a, b} then \sum ^{\bigstar} = \epsilon ,a,b,aa,ab,ba,bb,aaa,aab,..... Here can we take ba ? I mean placing doesn't matter ?$ On page 74 second para its given (a+( ... and na (v) = nb (v) , where v is any prefix of w } . I'm not getting this whole notation ,please explain thank you !
asked
Jan 16, 2018
in
Theory of Computation
by
_shashi
(
385
points)

52
views
theoryofcomputation
cfg
0
votes
0
answers
18
Chomsky Normal Form
asked
Dec 10, 2017
in
Theory of Computation
by
Sanjay Sharma
Boss
(
49.3k
points)

136
views
theoryofcomputation
cfg
cnf
0
votes
1
answer
19
UllmanChomsky Normal Form
If the start symbol derives epsilon.Can we eliminate all epsilons while converting to Chomsky Normal Form?Following question from ullman the answer given they have removed the epsilon.But I think if the start symbol derives epsilon,more accurately if L(G) contains epsilon we cannot remove it. S>ASBepsilon A>aASa B>SbSAbb
asked
Nov 25, 2017
in
Theory of Computation
by
Surajit
Active
(
3.7k
points)

166
views
theoryofcomputation
cfg
cnf
+4
votes
3
answers
20
TOC SAMPLE PRACTICE
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2w+1 (b) log2w (c) log2w−1 (d) None of these
asked
Nov 19, 2017
in
Theory of Computation
by
Pranav Madhani
Junior
(
745
points)

1.1k
views
theoryofcomputation
practice
sample
cfg
+1
vote
2
answers
21
TOC SAMPLE PRACTICE
Consider the language defined by the regular expression (a  b) * b+. Which of the following regular expressions also define that language? (i) (a*b+)  (b*b+) (ii) (ab bb)*b* (iii) (a  b  ba)*b+ (a) i only (b) i & ii only (c) iii ... Solution: Option (c) Need explanation why not all? we can obtain only b by taking (a  b) null it also applies to a option then why not a?
asked
Nov 19, 2017
in
Theory of Computation
by
Pranav Madhani
Junior
(
745
points)

294
views
theoryofcomputation
sample
cfg
practice
0
votes
1
answer
22
Sample Practice
Consider this grammar: S → SS  a How many derivation trees are possible for a4? (a) 3 (b) 4 (c) 5 (d) 6 how to generalize for any values if a^5 or a^7 is there any general formulae?
asked
Nov 18, 2017
in
Theory of Computation
by
Pranav Madhani
Junior
(
745
points)

261
views
cfg
sample
practice
theoryofcomputation
0
votes
1
answer
23
Toc Gate 2018 sample practice
Consider 2 regular expression: i. ϕ* + a+ + b+ + (a + b)+ → r1 ii. ϕ+ + a* + b* + (a + b)* → r2 (a) L(r1) = L(r2) (b) L(r1) ⊆ L(r2) (c) L(r1) ⊇ L(r2) (d) None of above Solution: Option (a) how need explanation? wont answer be c?
asked
Nov 17, 2017
in
Theory of Computation
by
Pranav Madhani
Junior
(
745
points)

261
views
theoryofcomputation
sample
gate2018
theoryofcomputation
practice
cfg
0
votes
1
answer
24
#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
Loyal
(
8.4k
points)

101
views
theoryofcomputation
contextfreelanguages
contextfreegrammars
cfg
+1
vote
1
answer
25
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
(
113
points)

81
views
theoryofcomputation
cfg
contextfreegrammars
+2
votes
1
answer
26
Raghunath Tiwari(NPTEL NOC Chomsky Normal Form)
S>ASB A>aASA  a  ϵ B>SbS  A  bb Convert this grammar into Chomsky Normal Form
asked
Jul 3, 2017
in
Theory of Computation
by
Veeplob Singh
(
47
points)

224
views
theoryofcomputation
cfg
cnf
grammar
0
votes
1
answer
27
#TOC#Hopcroft and ullman #cfg
How to solve this? Design CFG for the language {aibjck  i=j+k}
asked
Apr 13, 2017
in
Theory of Computation
by
csuprriya
(
89
points)

72
views
theoryofcomputation
cfg
0
votes
1
answer
28
context free grammar
Do the following productions mean the same Bb>bb and B>b My doubt is that will the first production be used only when we have b in the follow of B or it can be used in any case. If it can be used in any case then will the first production be equal to second production.
asked
Apr 4, 2017
in
Theory of Computation
by
Srinivas Rao
(
385
points)

231
views
cfg
contextfreelanguages
theoryofcomputation
+1
vote
1
answer
29
context free grammar
Construct contextfree grammars to accept the following languages. $\begin{align*} \large L = \left \{ 0^i1^j2^k \;\;  \;\; i \neq j \;\; or \;\; j \neq k \right \} \end{align*}$
asked
Mar 25, 2017
in
Theory of Computation
by
gabbar
Junior
(
517
points)

228
views
cfg
contextfreelanguages
theoryofcomputation
0
votes
0
answers
30
Online Test Series
L1 = {an bm  n ≤ m ≤ 2n} L2 = {an bm│m≠n & m≠2n} Which of the following is true? A. Only L1 is CFG B. Only L2 is CFG C. Both are CFG D. None of them is CFG
asked
Jan 26, 2017
in
Theory of Computation
by
AmitPatil
(
285
points)

144
views
theoryofcomputation
cfg
normal
Page:
1
2
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged cfg
Recent Blog Comments
Hey all! I can't see the CS branch here? How...
it's depends year to year
What was the average cutoff that was maintained...
@Shivateja MST I don't think it will go high
http://univ.tifr.res.in/gs2020/Test_Results/INT_Sh...
50,741
questions
57,251
answers
198,044
comments
104,649
users