Skip to main content

Questions tagged [context-sensitive]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9 votes
3 answers
1k views

Context-sensitive grammar for the language of words concatenated with themselves

I'm looking for a context-sensitive grammar that describes the following language: $L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ . I've got problems with the fact that no rules such as $X \to \...
MrBolton's user avatar
1 vote
4 answers
3k views

Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$. I think it should be something like this \begin{align*} S &\to aA \mid a\\ aA&\to aaaA \mid aa \end{...
unnamed's user avatar
  • 65
10 votes
1 answer
5k views

Is there an example of a recursive language which is not context sensitive?

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for ...
Ivan Meza's user avatar
  • 103
7 votes
3 answers
3k views

How to generate a context sensitive grammar for www

I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages for example how do i proceed on this kind of question. Give a context-...
User_1234's user avatar
  • 145
4 votes
1 answer
110 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
1 answer
3k views

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$: $$ \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*} $$ I ...
Pavan Kumar Munnam's user avatar
0 votes
2 answers
772 views

Grammar for square numbers in unary

I have to write a grammar for the following language: $$\{1^{n^2} \mid n\geq 1 \}$$ I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as ...
Pranav Arora's user avatar
0 votes
1 answer
123 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
300 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
  • 327
22 votes
3 answers
596 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
Luke Mathieson's user avatar
15 votes
4 answers
5k views

Can someone give a simple but non-toy example of a context-sensitive grammar?

I'm trying to understand context-sensitive grammars. I understand why languages like $\{ww \mid w \in A^*\}$ $\{a^n b^n c^n \mid n\in\mathbb{N}\}$ are not context free, but what I'd like ...
BlueBomber's user avatar
  • 1,297
13 votes
2 answers
4k views

Are all context-sensitive languages decidable?

I was going through the Wikipedia definition of context-sensitive language and I found this: Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
bongubj's user avatar
  • 563
12 votes
2 answers
591 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
9 votes
1 answer
5k views

How to prove that context sensitive languages are closed under intersection and complement?

This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context ...
arty's user avatar
  • 193
8 votes
1 answer
328 views

Is unary language with polynomial power context sensitive?

I suppose that $\Sigma = \{a\}$. Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language. It ...
haleh's user avatar
  • 151
4 votes
1 answer
191 views

Is there a recommended process for designing CSGs (other than intuition)?

I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the ...
delrocco's user avatar
  • 207
4 votes
1 answer
275 views

Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$

I would like to get some help for finding the context-sensitive grammar for the language: $$L_1=\{a^ib^jc^{ij} \mid i,j\geq 0\}.$$ To answer the question before it's written here, yes I've tried to ...
Wanderer's user avatar
  • 279
3 votes
1 answer
1k views

Which properties of context sensitive languages are decidable?

There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable? $L_1 = \emptyset$ $L_1 = \Sigma^*$ $L_1 \cap L_2 = \...
Bharat Kul Ratan's user avatar
3 votes
1 answer
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 ...
Mithlesh Upadhyay's user avatar
2 votes
1 answer
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?
Apfelsaft's user avatar
2 votes
1 answer
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), ...
BlueBomber's user avatar
  • 1,297
1 vote
1 answer
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 ?
unknownUsername39493's user avatar
1 vote
0 answers
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 ...
vzn's user avatar
  • 11k
1 vote
0 answers
203 views

grammar for binary number in base n

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}...
hamid's user avatar
  • 21