Skip to main content

# Tag Info

## Hot answers tagged context-sensitive

11 votes
Accepted

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

Here's a more formal proof, by the standard trick of diagonalization (it must be folklore, but I saw it recently here) Let $G_1, G_2, ...$ be some enumeration of context sensitive grammars (convince ...
• 20.7k
9 votes

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

The intersections of context-free languages will never reach the full family of context-sensitive languages. The class of languages expressible as the intersection of $k$ context-free languages is ...
• 30.7k
8 votes

• 15.7k
3 votes

### Why do derivation tree not make sense for context-sensitive grammars?

Consider the CFG $$S\to AB \qquad A \to a \qquad B \to b$$ Here, it does not matter if we consider the derivation $$S \to AB \to aB \to ab$$ or $$S \to AB \to Ab \to ab$$ The order of the ...
• 14.6k
3 votes
Accepted

### Why do derivation tree not make sense for context-sensitive grammars?

For context-free grammars, the order in which you execute rules does not matter. Formally, let $\qquad \gamma = w_1 A_1 w_2 \dots w_{n-1} A_{n-1} w_n$ with $A_i \in N$ and $w_i \in T^*$ for all $i$. ...
• 72.4k
3 votes

### Is union of context-free and non-context-free languages non-context-free?

Not in general. Consider a language $L$ over some alphabet $\Sigma$ such that neither $L$ nor its complement $\overline{L}$ is a decidable language. It is obvious that neither of these languages can ...
• 2,506
3 votes
Accepted

• 4,817
3 votes
Accepted

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

The hint by Yuval in his comment is the right one. An approach to writing context-sensitive grammars is to design them like a machine. Send messages over the string. This is very close to writing a ...
• 30.7k

Only top scored, non community-wiki answers of a minimum length are eligible