Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [context-sensitive]

The tag has no usage guidance.

110 questions
Filter by
Sorted by
Tagged with
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 [,]. ...
• 103
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.
21 views

• 155
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?
• 155
130 views

### Context-sensitive grammar for function calls

Say we have context-free grammar for function declarations and calls (C-style) ...
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 (...
• 1
1 vote
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-...
• 181
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&...
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 ...
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}
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 ...
• 23
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
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 ...
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 ...
• 225
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-...
• 317
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 ...
1 vote
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 ...
1 vote
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, ...
• 13
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: ...
• 121
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) ...
1 vote
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 ...
• 1,132
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 ...
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 ...
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$...
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 ...
• 1
1 vote
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 ...
• 175
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?
• 37
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 ...
• 3
1 vote
1k views

1 vote
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 ...
• 1,200
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 ...
• 103
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 ...
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, ...
• 275
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-...
• 7,455
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.