The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
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
3
answers
1
GATE201931
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT contextfree? $\{ww^R \mid w \in \{a, b\}^*\}$ $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
385k
points)

1.5k
views
gate2019
theoryofcomputation
contextfreelanguage
0
votes
0
answers
2
Consider a language L = {xaybzc ((a ≤ b) or (a > b)) and (a ≠ c)}. Select the correct option.
asked
Jan 28
in
Theory of Computation
by
AVICS
(
7
points)

44
views
theoryofcomputation
contextfreelanguage
0
votes
2
answers
3
language
ϕ Σ* L X
asked
Jan 22
in
Theory of Computation
by
Rahul_Rathod_
Junior
(
565
points)

69
views
theoryofcomputation
regularlanguages
finiteautomata
regularexpressions
contextfreelanguage
0
votes
1
answer
4
TOC: CFG to GNF
$S>AA0$ $A>SS1$ Can someone please help to convert this CFG into Greiback normal formal (GNF)?
asked
Jan 22
in
Theory of Computation
by
chauhansunil20th
Active
(
4.8k
points)

33
views
theoryofcomputation
contextfreelanguage
cnf
gnf
0
votes
0
answers
5
A language is cfl or not
L = {a^(p+q) b^(p+q) a^p , p,q>=0} Which one of the following is true about L? L is a regular L is CFL but not regular L is not a CFL
asked
Jan 22
in
Theory of Computation
by
saptarshiDey
(
83
points)

21
views
theoryofcomputation
contextfreelanguage
regularlanguages
0
votes
1
answer
6
Context Free Languages
What is the difference between regular intersection and intersection? (I found out that CFL is closed under regular intersection but not under intersection) Thanks!
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
149
points)

19
views
contextfreelanguage
theoryofcomputation
contextfreelanguages
theory
+1
vote
1
answer
7
Context free language
Is this a deterministic context free language (DCFL) ? $a^{k}$  k is even Thanks!
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
149
points)

23
views
contextfreelanguage
theoryofcomputation
0
votes
1
answer
8
Cfg to and from pda
Do i have to study the conversation of pda to Cfg or cfg to pda? Is this an important concept with relevance to gate? I know how to individually make them though.
asked
Jan 21
in
Theory of Computation
by
Rhythm
(
75
points)

29
views
contextfreelanguage
pushdownautomata
0
votes
0
answers
9
CFL or CSL
Let L = $\{ a^n b^m  m , n \in \textbf{N} \text{ and m is multiple of n}\}$ How do we prove that this language is not CFL.
asked
Jan 18
in
Theory of Computation
by
!KARAN
Active
(
1.2k
points)

23
views
theoryofcomputation
contextfreelanguage
contextsensitivelanguages
0
votes
0
answers
10
Building a pushdown automata that receives L*
given a pushdown automata that receives L by getting to an accepting state, how can a pushdown automata be built, so that it accepts L*? (might use a “double bottom” if needed)?? i don’t know how to solve it and would appreciate any kind of help! studying for exam and must learn how to solve it
asked
Jan 16
in
Theory of Computation
by
agmund
(
7
points)

21
views
pushdownautomata
theoryofcomputation
contextfreelanguage
0
votes
1
answer
11
Test Series
If $L_1$ is DCFL and $L_2$ is context free language. Consider the below given statements Which is correct between these and why ? (S1 is correct.. but why ??) . I couldn’t understand the explanation given in the solution..
asked
Jan 14
in
Theory of Computation
by
Hardik Maheshwari
(
97
points)

47
views
contextfreelanguage
contextsensitive
context
deterministiccontextfreegrammars
theoryofcomputation
0
votes
0
answers
12
Made Easy test series
L1 is regular, L2 and L3 are CFL L1 is regular, L2 is CFL and L3 is CSL L1 is CFL but not regular,L2 is CSL but not CFL,L3 is CFL L1, L2 and L3 are CFL
asked
Jan 9
in
Theory of Computation
by
Sambhrant Maurya
Active
(
1.5k
points)

37
views
madeeasytestseries
regularlanguages
contextfreelanguage
0
votes
0
answers
13
Context free languages
{x w c w1, where x,w belong to {a,b}* and w1 is reverse of w} The language given is deterministic contextfree language or nondeterministic contextfree language?
asked
Jan 8
in
Theory of Computation
by
Iamniks4
(
63
points)

22
views
contextfreelanguage
0
votes
0
answers
14
DCFL or CFL?
Given that: { A^m B^n C^k/ if (k=even) then m=n} { A^m B^n C^k/ if (n=even) then m=k} Which of the above languages are DCFL? According to me it is CFL as we have to first count k and then compare other inputs.. same for second language ... is both are DCFL? it is only possible if skip path is exists here? does it exist for DCFLs? so confused please guide me? if given answer is correct?
asked
Jan 3
in
Theory of Computation
by
S Ram
Active
(
1.9k
points)

121
views
theoryofcomputation
dcfl
contextfreelanguage
0
votes
1
answer
15
Madeasy test series
Does equivalence of CFG decidable ? That is for two CFG G1 and G2 L(G1)= L(G2)? And if it is DCFG than is it decidable.
asked
Dec 30, 2018
in
Theory of Computation
by
Ayan21
(
107
points)

53
views
decidability
theoryofcomputation
contextfreelanguage
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
16
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_
Junior
(
565
points)

52
views
grammar
contextfreelanguage
dcfl
cfg
0
votes
1
answer
17
Context free language Question
please provide solution for given quesion.
asked
Dec 16, 2018
in
Theory of Computation
by
Dharmesh Gusai 1
(
141
points)

39
views
contextfreelanguage
theoryofcomputation
+1
vote
0
answers
18
CONVERT CFG TO GNF
S→ AB A→ BSb B→ SAa INTO GNF
asked
Dec 14, 2018
in
Theory of Computation
by
Menon Karthik
(
41
points)

64
views
gnf
cnf
theoryofcomputation
contextfreelanguage
+1
vote
1
answer
19
TOC Which is(are) regular? Please explain 1 and 4.
Which of the following languages is regular? L = { bba (ba)* a^n1  n> 0 } L = {a^nb^n  n < 1000 } L = {a^nb^k  n is odd or k is even } L = {wxw^R  w,x ∈(0+1)* } 1, 3 and 4 2, 3, 4 2, 3 1, 2, 3, 4
asked
Dec 13, 2018
in
Theory of Computation
by
rahuljai
(
437
points)

99
views
contextsensitive
regularlanguages
contextfreelanguage
theoryofcomputation
regularexpressions
0
votes
0
answers
20
Draw PDA for this
L = {a^m b^n c^k=m+n }  m >= 0 and n >= 0  Please draw PDA for this Language!
asked
Dec 12, 2018
in
Theory of Computation
by
Guilherme Zanini Mor
(
9
points)

49
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dcfl
0
votes
0
answers
21
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
(
437
points)

58
views
pushdownautomata
theoryofcomputation
contextfreelanguage
grammar
cfg
+2
votes
1
answer
22
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, 2018
in
Theory of Computation
by
Prince Sindhiya
Loyal
(
6.2k
points)

77
views
zeal
test
series
contextfreelanguage
closureproperty
0
votes
2
answers
23
Decidability
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
asked
Nov 1, 2018
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.3k
points)

99
views
decidability
theoryofcomputation
contextfreelanguage
0
votes
0
answers
24
Decidability
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?
asked
Nov 1, 2018
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.3k
points)

54
views
decidability
theoryofcomputation
contextfreelanguage
0
votes
1
answer
25
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, 2018
in
Theory of Computation
by
saptarshiDey
(
83
points)

39
views
theoryofcomputation
contextfreelanguage
0
votes
0
answers
26
Ace Book
asked
Oct 28, 2018
in
Theory of Computation
by
abhishek1995_cse
(
169
points)

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

26
views
theoryofcomputation
contextfreelanguage
0
votes
1
answer
28
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, 2018
in
Theory of Computation
by
abhishek1995_cse
(
169
points)

66
views
contextfreelanguage
regularlanguages
theoryofcomputation
Page:
1
2
3
4
5
6
...
12
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
Need suggestions for what to do next after Gate ??
For GATECSE Admissions 2019
Challenge to GATE keys: Question 26, If you also want to challenge the same, as I did!
How to follow Standard Textbooks?
Gate contest link is now open
Follow @csegate
Recent questions tagged contextfreelanguage
Recent Blog Comments
Well it is quite nostalgic for me as if I have...
See in recent posts "For GATE CSE Admissions 2019"
which ppt are you referring to, can you share the...
I am not a ranker so you might not believe on my...
What is the status on appsgate website? I...
47,932
questions
52,335
answers
182,384
comments
67,815
users