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

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

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

287 views

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

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

866 views

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

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

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

699 views

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

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

154 views

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

212 views

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

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

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

570 views

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

519 views

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

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

518 views

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

1.3k views

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

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

2.5k views

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

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

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

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

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

2.5k views

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

677 views

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

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

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

1.2k views

Page:

Recent questions tagged context-sensitive