Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [context-sensitive]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
49 views

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Consider the language $L$ over the alphabet (,[,),] such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,]. ...
kerzol's user avatar
  • 103
-4 votes
1 answer
54 views

Creating a context-sensitive grammar (CSG) for the language L = {anbna2n: n ≥ 1}

Need a grammar that can create this language, I am having issues getting a language to work and was looking for help.
user168937's user avatar
2 votes
1 answer
21 views

Valid rules in CSG

In the book of Hopcroft-Ullman (the 1979 edition) there is a rule $Da\rightarrow aaD$ in the example of the CSL language $a^{2^i}$. Valid rules in CSG have the form $\alpha A \beta\rightarrow \alpha\...
Ricardo Wehbe's user avatar
0 votes
1 answer
70 views

How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

I have been trying to understand how the language $L = \{a^m b^n c^p d^q \mid m*n=p+q\}$) is context-sensitive? I first encountered this question here. Would be grateful if you could provide some ...
yash's user avatar
  • 1
1 vote
1 answer
100 views

Language of equal numbers of as, bs, cs in any order not context-sensitive?

In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $L = \{ w \in \{a,b,c\}^*\ |...
Barney's user avatar
  • 155
-1 votes
1 answer
89 views

Is { a^nb^na^n} a context-sensitive language?

The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language. I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?
Barney's user avatar
  • 155
2 votes
2 answers
130 views

Context-sensitive grammar for function calls

Say we have context-free grammar for function declarations and calls (C-style) ...
Konstantin Vladimirov's user avatar
0 votes
0 answers
40 views

Devising a grammar for language L = { a^xb^ya^xb^y | x, y >= 0 }

I've been trying to come up with a proper grammar for this sort of language: L = { aˣbʸaˣbʸ | x, y >= 0 } I have failed to find a way to enforce consistent generation of terminals on either part (...
MWR_'s user avatar
  • 1
1 vote
0 answers
60 views

minimum number of non-terminals so that for all context-sensitive languages there is a non-contracting grammar

Every context-sensitive language $\subseteq \Sigma^* = \{a,b\}^*$ can be expressed using an essentially non-contracting grammar. With just one non-terminal symbol, we can't express all context-...
user126100's user avatar
4 votes
1 answer
111 views

Are the set of all Bitcoin addresses a context-sensitive language?

This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
Nathan Lim's user avatar
0 votes
1 answer
1k views

How to prove ww^r is context free using pumping lemma for context free languages

I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could ...
Pratik Hadawale's user avatar
-3 votes
1 answer
731 views

What's grammar for a^n b^n c^n d^n

What wiil be grammar rules for the language L={a^n b^n c^n d^n; n>0}
Sasffef's user avatar
0 votes
1 answer
122 views

Context Sensitive Grammar for $x \# x^R \# x$

This language is given. $L = \{\; x \# x^R \# x \mid x\in \{a,b\}^*\;\}$ I have to figure out a context sensitive grammar for it. I've tried several rules already but it's hard to make a copy of the ...
GR33NTE4's user avatar
0 votes
1 answer
492 views

Intersection between CSL and CFL?

I am trying to find a proof of A ∩ B where A is a CSL and B is a CFL. Also I know that CFL is a strict subset of CSL. Does that mean that their intersection will give CFL. I am stuck
glitch_123's user avatar
0 votes
1 answer
399 views

How to find context sensitive grammar for words like ww? [duplicate]

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammar, I've done some exercises pretty well and was able to do some of the ...
NumberAddicted's user avatar
0 votes
1 answer
58 views

Why do non Context Free languages need more stacks?

In an example question sheet for my exams our professor included “Know to explain why for non CF languages 1 stack is not enough.” We haven’t delved into CS and reclusively enumerable languages much ...
Tita's user avatar
  • 225
0 votes
1 answer
291 views

Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-...
S. M.'s user avatar
  • 317
4 votes
1 answer
74 views

Can you diagonalize a language out of CSL?

In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
Hugolin Bergier's user avatar
1 vote
1 answer
167 views

Easy-to-prove example of non-contextual language

When studying Chomsky's hierarchy of languages (starting from type 3), I find enlightening to encounter some language that can't belong to the current type but which very obviously belong to the next ...
Thomas Baruchel's user avatar
1 vote
3 answers
129 views

A non-CFL over {a,b,c} with a non-CFL complement?

I understand uncountably many such languages exist, and the rationale for it is clear to me. I just cannot think of one trivial, easy-to-prove example. For instance, the complement of a^nb^nc^n is CF, ...
Selby8's user avatar
  • 13
12 votes
2 answers
584 views

What is the closure of context-free languages under finite intersections?

Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive. So this leads to the question: ...
gewo's user avatar
  • 121
3 votes
1 answer
156 views

Closure of context-sensitive languages under inverse language substitution

We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) ...
HighAsAKiteOnMath's user avatar
1 vote
1 answer
782 views

Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text

I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds. Every context-sensitive language L is ...
Abhishek Ghosh's user avatar
-1 votes
2 answers
2k views

Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$

I tried many grammars and so far I got this one: \begin{align} &S \to aXbZ \mid abc \\ &XZ \to Ybcc \\ &Xb \to bX \\ &bY \to Yb \\ &aY \to aa \mid aaX \end{align} Is my grammar ...
James Tan's user avatar
0 votes
0 answers
38 views

Deterministic CSL = semi Deterministic CSL

How can it be proven that a deterministic CSL = semi-deterministic CSL? Does that imply that a CSL = semi CSL? Would I need to build a Turing machine, since a language accepted by a Turing machine is ...
Maxim Jorje's user avatar
0 votes
0 answers
165 views

Proof that CSL ⊊ REC

I'm trying to prove that a context sensitive language ⊊ Turing-acceptable language. I was thinking of working out the complement of the language $A$, where $A$ consists of all words $w$ such that $M_w$...
Mago12243's user avatar
0 votes
0 answers
21 views

generating strings from this formal grammar [duplicate]

Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
ceen's user avatar
  • 1
1 vote
0 answers
56 views

A Formal Grammar: defining English counting numbers?

I would like to define a grammar that produces and recognizes the counting numbers of the English language. I created the production rules below based on the assumption this is context-free, but I am ...
Nick's user avatar
  • 175
2 votes
1 answer
115 views

How can I show that this language is context sensitive?

I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
Cheia's user avatar
  • 37
0 votes
1 answer
3k views

{a^n b^n c^n | n>=1} - PDA

I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive. How I attempted it ...
Atom's user avatar
  • 3
1 vote
1 answer
1k views

How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?

This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
oldsailorpopoye's user avatar
0 votes
2 answers
418 views

How do Context Sensitive Grammar systems work?

The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result ...
LabGecko's user avatar
  • 103
1 vote
2 answers
1k views

Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?

Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get ...
A Paul's user avatar
  • 176
1 vote
2 answers
184 views

Is escaping a concept in CS?

I understand "escaping data" as making an exception when matching data; for example, if a program can't match data wrapped in some character/s (such as single and/or double quotes) without ...
George's user avatar
  • 45
2 votes
1 answer
4k views

Difference between linear bound automata and a Turing machine

Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a ...
Vamsi Shankar's user avatar
1 vote
1 answer
67 views

Language of context-sensitive grammar

I have the following context-sensitive grammar: $$ \begin{align*} &S \to xSy \mid a \mid b \\ &Xa \to aa \\ &Xb \to bb \\ &Y \to a \end{align*} $$ I know what it does, as it always ...
GuardGoose's user avatar
0 votes
1 answer
120 views

Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

I am trying to find a context sensitive grammar for the type-1 language $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$ I can construct the first part with \begin{align*} S &\to aSbB \mid B \...
Manuel Schmidt's user avatar
1 vote
1 answer
306 views

Context Sensitive Grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$

I have been trying to find a context sensitive grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$ for some time but I cannot get it done. Any ideas ?
unknownUsername39493's user avatar
0 votes
1 answer
52 views

What is the relation between a programming language and the language of its input?

I find some references say that all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything ...
Blanco's user avatar
  • 623
-4 votes
1 answer
101 views

How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5

Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well. A substitution rule describes how to take a sequence of ...
pblpbl's user avatar
  • 53
2 votes
1 answer
173 views

An example of a context-sensitive grammar for a given language

Consider this language: $L = \{a^nb^ma^nb^m \mid n,m \ge 1\}$. Can we give for this language a context-sensitive grammar?
Apfelsaft's user avatar
0 votes
1 answer
198 views

Examples of Regular, Context-free and Context-sensitive languages

Assume the languages: $$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \,...
Andrew's user avatar
  • 161
2 votes
1 answer
86 views

Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)

I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer): Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}...
Edmundo Del Gusto's user avatar
1 vote
2 answers
247 views

Doubt regarding Chomsky Hierarchy, CFG and CSG

I was following a discussion on a website, where a fellow scholar claims that this grammar S→ aAa | bAb | ϵ A→aA | bA |ϵ is not CSG, so it should also NOT be a CFG. But this grammar properly ...
Turing101's user avatar
  • 1,200
0 votes
2 answers
90 views

What makes a common programming language non-context-sensitive but RE?

I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine. But I cannot pinpoint what aspect makes a programming ...
Gwangmu Lee's user avatar
6 votes
1 answer
2k views

A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...
Andrey Lebedev's user avatar
0 votes
1 answer
32 views

Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?

Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, ...
user2277550's user avatar
4 votes
1 answer
108 views

Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?

In Wikipedia of Kuroda normal form, it says A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-...
xskxzr's user avatar
  • 7,455
3 votes
3 answers
176 views

How to give a context-sensitive grammar for a^nba^nba^nb?

I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.
Apfelsaft's user avatar
0 votes
2 answers
1k views

Are Context Sensitive Languages Turing Complete? [duplicate]

Related questions: Can regular languages be Turing complete? Why are Linearly Bounded Turing Machines more powerful than Finite State Automata? https://stackoverflow.com/questions/14589346/is-c-...
user's user avatar
  • 215