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
Lists
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 contextfreelanguage
0
votes
0
answers
1
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
1 day
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
757
points)

17
views
theoryofcomputation
contextfreegrammars
contextfreelanguage
cfg
pushdownautomata
0
votes
1
answer
2
Theory of Computation
$L1= \left \{ a^m b^n c^n d^m  m \neq n \right \}$ $L2= \left \{a^i b^j c^k  (i<=j)or (j<=i), j=k \right \}$ $L3= \left \{a^i b^j c^k i=j, j<k \right \}$ The number of the above languages that are context free are ?
asked
2 days
ago
in
Theory of Computation
by
Priyam Pandey
(
61
points)

66
views
contextfreelanguage
theoryofcomputation
0
votes
0
answers
3
CFL with Empty Stack or Final State
$1)$"We can solve same PDA with empty stack and using final state" Can give an example of such language? Where is the difference between solving a pda with empty stak and by accepting final state? I got this link but without ... acceptancebyemptystackandfinalstate $2)$If language has prefix property, why it cannot be solved with empty stack?
asked
Oct 4
in
Theory of Computation
by
srestha
Veteran
(
98.5k
points)

45
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
4
self doubt
name and explain the language which are context free,context sensitive i.e. FORTRAN is CSL, now tell me about c,cobol,c++,java and any other language which you can explain etc https://gateoverflow.in/80293/gate19871xiii
asked
Sep 30
in
Theory of Computation
by
Gurdeep Saini
Junior
(
829
points)

12
views
contextfreelanguage
identifyclasslanguage
0
votes
0
answers
5
CFGDoubt
$L=a^mb^nc^pd^q  m+p=n+q, m,n,p,q>=0$ is the language CFG or CFL?
asked
Sep 26
in
Theory of Computation
by
aditi19
Junior
(
863
points)

30
views
contextfreelanguage
0
votes
0
answers
6
Context free languages
X belongs to {a,b}* such that n(a)<n(b)<2n(a) is a CFL. Please somebody explain the push and pop sequences of the alphabets on the stack. I'm not being able to visualise, how it is CFL?
asked
Sep 18
in
Theory of Computation
by
aambazinga
Active
(
1.2k
points)

11
views
contextfreelanguage
theoryofcomputation
+1
vote
0
answers
7
Michael sipser
I read this excerpt from sipser book We write a,b → c to signify that when the machine is reading an a from the input, it may replace the symbol b on the top of the stack with a c. Any of a, b, and c may be ε. If a is ε, the machine ... using any stack symbol as written here that top of stack might be epsilon if we don't want to consume it. If someone can clear my doubt. Thanks
asked
Sep 15
in
Theory of Computation
by
sushmita
Boss
(
14.7k
points)

10
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
8
Closure Property
If L1 is CSL and L2 is CFL, then which of the following is correct ? A.L1'  L2 is CSL always B. L1  L2' is CSL always C. L1 intersection Regular is Regular always D. L1.L2 is CSL but not CFL
asked
Sep 9
in
Theory of Computation
by
Na462
Loyal
(
6.5k
points)

69
views
theoryofcomputation
contextfreelanguage
closureproperty
0
votes
0
answers
9
peter linz
The language L1={a^n b^n} union {b} The language L2={a^n b^n} union {a} They both are deterministic CFL. Am i right?
asked
Sep 9
in
Theory of Computation
by
sushmita
Boss
(
14.7k
points)

36
views
theoryofcomputation
peterlinz
contextfreelanguage
0
votes
0
answers
10
self doubt
Consider the Context free language which has equal no of as and bs. eg abab Since a proper prefix ab also belongs to this language, this language does not satisfy prefix property as far as i understand. But we can clearly draw a deterministic PDA ... with empty stack for CFL without prefix property. But above example forms a contradiction. Please resolve my doubt. I am getting confused.
asked
Sep 8
in
Theory of Computation
by
sushmita
Boss
(
14.7k
points)

53
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
11
PDADoubt
L=$a^mb^n$  m!=n is the following DPDA correct for the mentioned language?
asked
Sep 3
in
Theory of Computation
by
aditi19
Junior
(
863
points)

23
views
pushdownautomata
contextfreelanguage
0
votes
0
answers
12
DoubtPDA
what is the PDA for {L=$a^mb^n$ m>n}
asked
Sep 2
in
Theory of Computation
by
aditi19
Junior
(
863
points)

66
views
pushdownautomata
theoryofcomputation
contextfreelanguage
0
votes
1
answer
13
Non inherently ambiguous
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
6.5k
points)

35
views
contextfreelanguage
theoryofcomputation
inherentlyambiguous
0
votes
0
answers
14
Parsing
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?
asked
Aug 31
in
Compiler Design
by
Mizuki
Junior
(
839
points)

28
views
compilerdesign
parsing
contextfreelanguage
pushdownautomata
theoryofcomputation
0
votes
0
answers
15
DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ? I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
asked
Jul 28
in
Theory of Computation
by
Matrix
(
63
points)

40
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dpda
+1
vote
2
answers
16
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
(
155
points)

104
views
theoryofcomputation
regularlanguages
contextfreelanguage
grammar
0
votes
1
answer
17
self made doubt
How to know that the language needs 1 stack or more than one stack in order to know about it is regular, contextfree or not. example L1={$a^i b^j c^k│i<j<k$} L2={$a^i b^j c^k│i<j \ or \ k<j$} L3={$a^i b^j c^k│i<j \ and \ k<j$}
asked
Jun 11
in
Theory of Computation
by
Divyanshum29
Junior
(
567
points)

68
views
contextfreelanguage
regularlanguages
theoryofcomputation
0
votes
2
answers
18
Theory Of Computation Doubt.
I saw some where that a language which accepts $a^{n^{2}}  n \geq1$ is not context free Language and not regular language. is it not a language that has at least one $'a'$ as the string?. It should be regular as well according to this Logic right. Please correct me if wrong.
asked
Jun 3
in
Theory of Computation
by
abhiram144
(
63
points)

53
views
theoryofcomputation
contextfreelanguage
0
votes
2
answers
19
Ambiguous and unambiguous grammar
If a grammar( $CFG$ ) has more than one Right most derivation, Can it be called ambiguous ? Or we say a grammar is ambiguous only when it has more than one left most derivation ?
asked
May 28
in
Compiler Design
by
Rahul Ranjan 1
(
151
points)

68
views
theoryofcomputation
contextfreelanguage
compilerdesign
+2
votes
2
answers
20
Grade up topicwise questions
L1={a^n b^n c ^mm>=0 and n>=0} L2={a^m b^ n c^ nn>=0 and m>=0} If L3=L1UL2 then how many of L1,L2,L3 are context free languages? A)1 (B)2 (C)3 (D) none Answer given option C. Please explain?
asked
May 8
in
Theory of Computation
by
Sona Barman
Active
(
1.2k
points)

123
views
theoryofcomputation
contextfreelanguage
0
votes
4
answers
21
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
(
679
points)

155
views
contextfreelanguage
theoryofcomputation
grammar
+1
vote
1
answer
22
which of the following statements are correct in context of LR parser ?
asked
Apr 30
in
Compiler Design
by
radha gogia
Loyal
(
7.5k
points)

63
views
compilerdesign
contextfreelanguage
0
votes
1
answer
23
Context Free Languages
Answer with explanation will be acknowledged.
asked
Apr 13
in
Theory of Computation
by
Subham Nagar
Junior
(
679
points)

64
views
contextfreelanguage
theoryofcomputation
contextfreelanguages
0
votes
1
answer
24
Introduction to Computer Theory
Give CFG for the following language L =$ {(a^{m})(b^{m+n})(c^{n})  m,n= 0,1,2,.....}$
asked
Apr 12
in
Theory of Computation
by
The Capricorn
(
147
points)

57
views
theoryofcomputation
contextfreelanguage
0
votes
1
answer
25
Exam  Foundation of Computing  2018
Find a contextfree grammar for the following language: L = { a^m b^m c^k  k <= m } (in order to show that the language is contextfree)
asked
Apr 11
in
Theory of Computation
by
Melissa
(
7
points)

45
views
contextfreelanguage
contextfreegrammars
+1
vote
0
answers
26
whether the given languages are context free or not
asked
Apr 8
in
Theory of Computation
by
Sambit Kumar
Active
(
4.1k
points)

101
views
theoryofcomputation
contextfreelanguage
+2
votes
0
answers
27
Theory of computations(CFG)
$L1$ has the following grammar: $S \rightarrow aB/BA$ $A\rightarrow bAA/aS/a$ $B\rightarrow b/bS/aBB$ can someone help me with an easy way to get the general expression for string belonging to this language. Or some hint that how should I proceed to solve this question.
asked
Mar 29
in
Theory of Computation
by
hrcule
(
287
points)

50
views
theoryofcomputation
contextfreelanguage
+4
votes
1
answer
28
Context Free Languages
Which of these languages are deterministic? $L_{1} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ b \right \}$ $L_{2} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ a \right \}$
asked
Mar 28
in
Theory of Computation
by
Mk Utkarsh
Boss
(
20.2k
points)

135
views
contextfreelanguage
theoryofcomputation
+2
votes
0
answers
29
CFG to GNF
Convert the given CFG to GNF. $S \rightarrow MN$ $M\rightarrow aMb\epsilon $ $N\rightarrow aNb\epsilon $
asked
Mar 25
in
Theory of Computation
by
Mk Utkarsh
Boss
(
20.2k
points)

166
views
theoryofcomputation
contextfreelanguage
cnf
gnf
0
votes
0
answers
30
Peter Linz Exercise 6.1.9
Eliminate all unitproductions from the grammar $S \rightarrow a  aA BC,$ $A \rightarrow aB  λ,$ $B \rightarrow aA,$ $C \rightarrow aCD,$ $D \rightarrow ddd $
asked
Mar 23
in
Theory of Computation
by
Mk Utkarsh
Boss
(
20.2k
points)

70
views
theoryofcomputation
peterlinz
contextfreelanguage
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
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
Follow @csegate
Gatecse
Recent questions tagged contextfreelanguage
Recent Blog Comments
Nice 2 know. You are welcome. :)
Hello @Arjun, I got books now...thanks for your...
You may contact FedEx local delivery office. It...
Yes you are right, it's showing this status from...
FedEx delivery is shown and as per that it is out...
40,958
questions
47,599
answers
146,673
comments
62,335
users