# Questions tagged [context-sensitive]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
1k views

366 views

### What is language of repeat(L) = {ww | w ∊ L}? [closed]

What is language of repeat(L) = {ww | w ∊ L} ? My try: I know it {ww | w ∊ (a,b)*} is context sensitive language. Here , what is meant by "repeat(L)" ? Can you explain it ? It is not a ...
175 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?
814 views

### Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar

I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form: $$\alpha \rightarrow \beta$$ where $|\alpha| \leq |\beta|$ (called a monotonic grammar), ...
• 1,297
1 vote
308 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 ?
1 vote
79 views

### Notable decidable operations on context-sensitive languages [closed]

It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable. What are notable or ...
• 11k
1 vote
given a binary number b, is there any grammar that generates the languages of $1^x$ where $x$ is $b$ in base $n$ ($n \in \mathbb{N}$) e.g. if $b$ is 1100, the grammar should generates \$11,1^{12},1^{36}...