Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged context-sensitive
2
votes
0
answers
1
Is it CFL or CSL?
Is {$a^nb^nc^n$ | $n>=0$} CSL? After comparing both a and b, stack would be empty. So it can’t be CFL. So it is CSL or recursive. And does this language require more than 1 stack? Please tell how would check for the grammer of this language even if it is in CSL. Thank you
h4kr
asked
in
Theory of Computation
Dec 23, 2022
by
h4kr
116
views
theory-of-computation
context-free-language
context-sensitive
pushdown-automata
3
votes
2
answers
2
Is it also CSL?
Is the following Language, L = {xxxx | x ∈ {0, 1}*} CSL or not? I saw a explanation say that it’s REC, but it didn’t say anything about it not being CSL and I used to think strings like {xx | x ∈ {0, 1}*} are CSL where the same strings keep repeating [like x here]. So is it CSL and please do also tell is there a rule to figure that out?
h4kr
asked
in
Theory of Computation
Dec 18, 2022
by
h4kr
260
views
theory-of-computation
context-sensitive
recursive-and-recursively-enumerable-languages
0
votes
2
answers
3
Theory of Computation | Automata
L= {$a^nb^nc^nd^n; n\geq 0$} Given Language is a CSL TRUE FALSE
Souvik33
asked
in
Theory of Computation
Dec 12, 2022
by
Souvik33
287
views
theory-of-computation
context-sensitive
2
votes
1
answer
4
ace academy ToC
I don’t get the explanation, How do you categorize grammer on the basis of production?
h4kr
asked
in
Theory of Computation
Dec 4, 2022
by
h4kr
231
views
theory-of-computation
context-sensitive
grammar
ace-test-series
0
votes
1
answer
5
Context Sensitive Grammars
Is the following CSG for a^n b^n c^n correct? S->aSbC|abc Cb->bC C->c If not please explain why?
preethi01
asked
in
Theory of Computation
Jan 29, 2022
by
preethi01
866
views
theory-of-computation
context-sensitive
0
votes
1
answer
6
Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.
UltraRadiantX
asked
in
Theory of Computation
Oct 9, 2021
by
UltraRadiantX
334
views
theory-of-computation
context-free-language
context-sensitive
0
votes
1
answer
7
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..
Hardik Maheshwari
asked
in
Theory of Computation
Jan 14, 2019
by
Hardik Maheshwari
1.1k
views
context-free-language
context-sensitive
context
deterministic-context-free-grammars
theory-of-computation
2
votes
1
answer
8
TOC Which is(are) regular? Please explain 1 and 4.
Which of the following languages is regular? L = { bba (ba)* a^n-1 | 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
rahuljai
asked
in
Theory of Computation
Dec 13, 2018
by
rahuljai
699
views
context-sensitive
regular-language
context-free-language
theory-of-computation
regular-expression
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
abhishek1995_cse
asked
in
Theory of Computation
Oct 21, 2018
by
abhishek1995_cse
388
views
context-free-language
pushdown-automata
context-sensitive
0
votes
0
answers
10
Doubt in Grammar
What is the difference between phase structured grammar and phrase structured grammar?
goluabhinan
asked
in
Theory of Computation
Sep 16, 2018
by
goluabhinan
154
views
theory-of-computation
grammar
context-sensitive
compiler-design
0
votes
0
answers
11
Doubt in Grammar
Below is the grammar then find the language generated by given grammar S → ABC AB → aAx |bAy | ε xb → bx ya → ay C → ε yb → by xC → BaC aB → Ba yC → BbC bB → Bb xa → ax Correct option : (a) L = {w|w ∈ (a, b)∗, and xa(w) = xb(w)} (b) L = {w|w ⊆ (a, b)+, and w is a palandrom string (c) L = {w|w ⊆ (a, b)∗, and w = xx, where X = (a, b)∗} (d) None of the above
goluabhinan
asked
in
Theory of Computation
Sep 10, 2018
by
goluabhinan
212
views
theory-of-computation
grammar
context-sensitive
0
votes
2
answers
12
UGC NET CSE | July 2018 | Part 2 | Question: 37
Context sensitive language can be recognized by a Finite state machine Deterministic finite automata Non-deterministic finite automata Linear bounded automata
Pooja Khatri
asked
in
Theory of Computation
Jul 13, 2018
by
Pooja Khatri
1.8k
views
ugcnetcse-july2018-paper2
theory-of-computation
context-sensitive
0
votes
2
answers
13
context sensitive grammer
it is given that in csg if @-># then length of @ should be less or equal to # then how aaB->c is a csg???
Ravi prakash pandey
asked
in
Theory of Computation
Apr 7, 2018
by
Ravi prakash pandey
532
views
theory-of-computation
context-sensitive
1
vote
2
answers
14
Regular and CFL
LC may be CFL LC cannot be CFL LC may be regular LC may or may not be CFL
Parshu gate
asked
in
Theory of Computation
Dec 10, 2017
by
Parshu gate
570
views
theory-of-computation
context-free-language
context-sensitive
2
votes
1
answer
15
Doubt in CSL and CFL
$a) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ or\ j\ \neq k\ \}$ $b) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ and\ j\ \neq k\ \}$ a) CFL(union of two OR-ed comparisons ) b) CSL( Double comaprison ) Am I correct?
Tuhin Dutta
asked
in
Theory of Computation
Dec 4, 2017
by
Tuhin Dutta
519
views
theory-of-computation
context-sensitive
context-free-language
0
votes
0
answers
16
General syllabus doubt
Hello, The gate 2018 syllabus explicitly mentions regular languages, context free languages and turing machines. It does not say anything about context sensitive languages and linear bounded automata..How much of these topics should i study?..definitions? closure properties?
Tridhara Chakrabarti
asked
in
Study Resources
Nov 23, 2017
by
Tridhara Chakrabarti
436
views
context-sensitive
theory-of-computation
syllabus
gate2018-preparation
grammar
5
votes
1
answer
17
Regular and CFL
Let L={ai bj ck ┤|if j is odd then i=k} where i,j,k>0. Which of the following option is true about L? L is CSL but not CFL L is CFL but not DCFL L is regular L is DCFL but not regular
Parshu gate
asked
in
Theory of Computation
Nov 17, 2017
by
Parshu gate
518
views
theory-of-computation
regular-language
context-sensitive
context-free-language
0
votes
0
answers
18
Peter Linz Edition 4 Example 10.5 (Page No. 272)
Find a linear bounded automata that accepts the language 1. L={a^(n!) : n>=0} 2. L ={a^n : n is perfect square} Please explain.
Nikita888
asked
in
Theory of Computation
Nov 16, 2017
by
Nikita888
1.3k
views
theory-of-computation
context-sensitive
peter-linz
peter-linz-edition4
0
votes
1
answer
19
Language which is not a CSL but can be accepted by TM
Can anyone give me an example of a language which is not a CSL but can be accepted using a Halting TM?
Xylene
asked
in
Theory of Computation
Jun 15, 2017
by
Xylene
1.2k
views
theory-of-computation
context-free-language
pushdown-automata
context-sensitive
recursive-and-recursively-enumerable-languages
turing-machine
2
votes
3
answers
20
CSL and Regular language
if L1 = { anbncn | n>= 0 } and L2 = { anbmck | k,n,m>=0} L1 is CSL and L2 is regular. Now L3 = L1.(L2)*. Is L3 is regualar or CSL?
AnilGoudar
asked
in
Theory of Computation
May 10, 2017
by
AnilGoudar
2.5k
views
theory-of-computation
context-sensitive
regular-language
7
votes
3
answers
21
ISRO2017-11
Given the following statements S1 : Every context-sensitive language $L$ is recursive S2 : There exists a recursive language that is not context-sensitive Which statements are true? Only S1 is correct Only S2 is correct Both S1 and S2 are not correct Both S1 and S2 are correct
sh!va
asked
in
Theory of Computation
May 7, 2017
by
sh!va
5.6k
views
isro2017
theory-of-computation
context-sensitive
4
votes
0
answers
22
Are CSL, RE, Recursive languages closed under Subset operation?
Regular languages are not closed under Subset - Example anbn is subset of a*b* which is non-regular. DCFL/CFL languages are not closed under Subset - Example anbncn is subset of anbnc* which is non-cfl. Are the languages CSL,Recursive or Recursively Enumerable lanuages closed under Subset operation?
yg92
asked
in
Theory of Computation
Feb 8, 2017
by
yg92
2.4k
views
theory-of-computation
recursive-and-recursively-enumerable-languages
context-sensitive
context-sensitive-languages
closure-property
0
votes
1
answer
23
geeks mock 2017 #56
Which of the following statements is correct about context sensitive grammar? I) In a context sensitive grammar, ε can't be the right hand side of any production II) In a context sensitive grammar, number of grammar symbols on the left hand side of a production ... of non-terminals on the right hand side Isn't (II) (non contracting grammar is also CSL) and (IV) both are correct
Pankaj Joshi
asked
in
Compiler Design
Jan 15, 2017
by
Pankaj Joshi
2.6k
views
geeksforgeeks-test-series
compiler-design
context-sensitive
0
votes
0
answers
24
Virtual Gate Test Series: Theory Of Computation - Context Sensitive Grammar
How can L(G) be regular? If we derive bSb --> bAcAb, now we have Ab-->b but we do not have the production bA since G is all production except last. So there is no production for A or bA. How can we go further?
Purple
asked
in
Theory of Computation
Jan 12, 2017
by
Purple
282
views
theory-of-computation
context-sensitive
grammar
virtual-gate-test-series
10
votes
2
answers
25
Which of these languages are regular, CFL and CSL?
Consider the following statements: $L_1=\left\{\text{wxw$^R$|w$\in$(a,b)$^*$, x$\in$c }\right\}$ $L_2=\left\{\text{wy|w, y $\in$ (a,b)$^*$}\right\} $ ... free, $L_2$ and $L_3$ are regular and $L_4$ is context sensitive languages $L_1, L_4$ are context free, $L_2$ and $L_3$ is context sensitive languages
Mahesha999
asked
in
Theory of Computation
Dec 25, 2016
by
Mahesha999
2.5k
views
theory-of-computation
context-free-language
context-sensitive
3
votes
2
answers
26
How can I tell if these languages are context sensitive
How can I tell if languages $L_1$ and $L_2$ are Context Sensitive or not?
Mahesha999
asked
in
Theory of Computation
Dec 25, 2016
by
Mahesha999
677
views
theory-of-computation
context-sensitive
1
vote
1
answer
27
context sensitive language
L = { ${\epsilon }$ } is a a) regular b) CFL c) CSL d) recursive language
Neal Caffery
asked
in
Theory of Computation
Dec 2, 2016
by
Neal Caffery
923
views
theory-of-computation
identify-class-language
context-sensitive
3
votes
0
answers
28
GATE CSE 1990 | Question: 15b
Complete the following production rules which generate the language:$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$ where variables $R$ and $Q$ are used to move back and forth over the current string generated $S \rightarrow aYc$ ... $Qc \rightarrow cQ$ $Q \rightarrow R'c$ $cR' \rightarrow ...$ $bR' \rightarrow ...$ $aR' \rightarrow a...$
makhdoom ghaya
asked
in
Theory of Computation
Nov 26, 2016
by
makhdoom ghaya
517
views
gate1990
descriptive
theory-of-computation
grammar
context-sensitive
out-of-gate-syllabus
2
votes
1
answer
29
Why can't linear bounded automata accept an empty string?
The linear bounded automata (LBA) is defined as follows: A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in the definition of TM) with the restriction that ... explains why LBA cannot accept empty string (which is why CSG does not have lambda production). Can anyone explain?
Mahesha999
asked
in
Theory of Computation
Nov 20, 2016
by
Mahesha999
1.2k
views
theory-of-computation
context-sensitive
Page:
1
2
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
DRDO Scientist -B
ISRO Scientist-B 2023
BARC RECRUITMENT 2023
COAP Responses | GATE CSE 2023
Interview Experience : M.Tech AI at IIT Jodhpur, Self Sponsored
Subjects
All categories
General Aptitude
(2.8k)
Engineering Mathematics
(9.7k)
Digital Logic
(3.4k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.4k)
Others
(2.4k)
Admissions
(665)
Exam Queries
(1.0k)
Tier 1 Placement Questions
(17)
Job Queries
(77)
Projects
(9)
Unknown Category
(867)
Recent questions tagged context-sensitive
Recent Blog Comments
Indeed the reasons are valid, hope the positive...
@Shubham Sharma 2 Is it possible to get a...
are MSc.(CS) students eligible?
It is said that the gate score will have 80%...
Maybe we should raise our concern in Supreme...