# Tag Info

Accepted

### Class of the language only containing the empty string?

This issue is covered in wikipedia's article on noncontracting grammars. Such grammars do not allow deriving the empty string, which is no problem when one considers languages $L\subseteq A^+$. When ...
• 831
Accepted

### Can there be a context-sensitive pumping lemma?

Here is some evidence that there is no pumping lemma for the context-sensitive languages. Of course, an answer hinges on the question what constitutes a pumping lemma. The weakest reasonable ...
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.4k

• 270k
Accepted

### Grammar for square numbers in unary

Let $B$ stand for the beginning marker, $A$ stands for a single 1 to be added later, $D$'s are copier markers and $E$ be the end marker. $F$, $G$, $I$, $H$ markers are used to properly generate all $A$...
• 4,747

### What would a formal grammar for a binary file format look like?

The Chomsky hierarchy is a hierarchy of grammars described by a given formalism. The other grammar descriptions that you are giving (attribute grammars, ...) are not part of that formalism so they ...
• 3,004
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 ...