Tag Info

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

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.8k

• 15.7k

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
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.5k
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.8k
Accepted

• 39k