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
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 contextfreelanguage
0
votes
0
answers
1
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
in
Theory of Computation
by
rahuljai
(
43
points)

36
views
pushdownautomata
theoryofcomputation
contextfreelanguage
grammar
cfg
+2
votes
1
answer
2
gate zeal test TOC
select the correct statement NonCFL is closed under reversal operation . L=$ \{ \;0^n1^m0^m: n+m \; mod \;6 =2 \} $ is CFL but not regular. if L is context free and R and S are regular ,then MAJORITY(L,R,S)={ w w is in atleast two of R,L,S } is also context free (a) only i (b) only I and II (c) Only II and III (d) All
asked
Nov 25
in
Theory of Computation
by
Prince Sindhiya
Active
(
5.2k
points)

59
views
zeal
test
series
contextfreelanguage
closureproperty
0
votes
2
answers
3
Decidability
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
asked
Nov 1
in
Theory of Computation
by
Shamim Ahmed
Junior
(
935
points)

83
views
decidability
theoryofcomputation
contextfreelanguage
0
votes
0
answers
4
Decidability
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?
asked
Nov 1
in
Theory of Computation
by
Shamim Ahmed
Junior
(
935
points)

39
views
decidability
theoryofcomputation
contextfreelanguage
0
votes
1
answer
5
Complementation of a Language of a L
If L is any Language and L' be its complement. L is CFL. Which of these two statements is true: 1. For any value of L, L' is not in CFL 2. There exists atleast one value of L for which L' is not in CFL
asked
Oct 31
in
Theory of Computation
by
saptarshiDey
(
37
points)

27
views
theoryofcomputation
contextfreelanguage
0
votes
0
answers
6
Ace Book
asked
Oct 28
in
Theory of Computation
by
abhishek1995_cse
(
159
points)

49
views
contextfreelanguage
regularlanguages
theoryofcomputation
turingmachine
0
votes
1
answer
7
Context Free Grammar
L=0^i 1^j 2^k  i=j or j=k is the grammar DCFG?
asked
Oct 23
in
Theory of Computation
by
aditi19
Active
(
2k
points)

23
views
theoryofcomputation
contextfreelanguage
0
votes
1
answer
8
Ace book
The minimal finite automata accepting the set of all strings over {0,1} starting with a 1 that interpreted as the binary representation of an integer are congruent to 0 modulo 5 has ______ states. The ans is 7 but according to me modulo n has 5 states .?
asked
Oct 22
in
Theory of Computation
by
abhishek1995_cse
(
159
points)

53
views
contextfreelanguage
regularlanguages
theoryofcomputation
0
votes
0
answers
9
Ace Book
The complement of the language L containing an equal number of a's , b's and c's is a)regular b)context free c)context sensitive but not context free d)recursive and not a CFL
asked
Oct 21
in
Theory of Computation
by
abhishek1995_cse
(
159
points)

38
views
contextfreelanguage
pushdownautomata
contextsensitive
0
votes
0
answers
10
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
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
947
points)

34
views
theoryofcomputation
contextfreegrammars
contextfreelanguage
cfg
pushdownautomata
0
votes
1
answer
11
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
Oct 18
in
Theory of Computation
by
Priyam Pandey
(
111
points)

94
views
contextfreelanguage
theoryofcomputation
0
votes
0
answers
12
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
(
103k
points)

82
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
13
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
Active
(
5k
points)

18
views
contextfreelanguage
identifyclasslanguage
0
votes
0
answers
14
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
Active
(
2k
points)

34
views
contextfreelanguage
0
votes
0
answers
15
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.8k
points)

21
views
contextfreelanguage
theoryofcomputation
+1
vote
0
answers
16
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
(
15.2k
points)

12
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
17
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
(
7.4k
points)

76
views
theoryofcomputation
contextfreelanguage
closureproperty
0
votes
0
answers
18
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
(
15.2k
points)

38
views
theoryofcomputation
peterlinz
contextfreelanguage
0
votes
0
answers
19
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
(
15.2k
points)

56
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
20
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
Active
(
2k
points)

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

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

53
views
contextfreelanguage
theoryofcomputation
inherentlyambiguous
0
votes
0
answers
23
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
Active
(
1k
points)

44
views
compilerdesign
parsing
contextfreelanguage
pushdownautomata
theoryofcomputation
0
votes
0
answers
24
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
(
67
points)

72
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dpda
+1
vote
2
answers
25
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
(
263
points)

113
views
theoryofcomputation
regularlanguages
contextfreelanguage
grammar
0
votes
1
answer
26
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
(
747
points)

69
views
contextfreelanguage
regularlanguages
theoryofcomputation
0
votes
2
answers
27
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)

56
views
theoryofcomputation
contextfreelanguage
0
votes
2
answers
28
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)

87
views
theoryofcomputation
contextfreelanguage
compilerdesign
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
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged contextfreelanguage
Recent Blog Comments
@
44,054
questions
49,578
answers
162,842
comments
65,775
users