Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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 ...
Ran G.'s user avatar
  • 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 ...
Hendrik Jan's user avatar
  • 30.8k
8 votes

A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(...
Yuval Filmus's user avatar
8 votes
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 ...
Georg Zetzsche's user avatar
7 votes
Accepted

Why can't linear bounded automata accept an empty string?

Linear-bounded automata are able to accept the empty string. The equivalence between linear-bounded automata and context-sensitive grammars needs to be cognizant of this discrepancy between the two ...
Yuval Filmus's user avatar
6 votes
Accepted

Is the set of strings $0^{2k}10^{2k}10^{k}$ for $k \geq 0$ context-free?

There is no context free grammar that can accept those two sets. You can show that using the pumping lemma for CFLs. Suppose $L = \{x \in \{0,1\}^* \mid x = 0^{2k}10^{2k}10^{k}, k \geq 0 \}$ Let $n$...
skankhunt42's user avatar
6 votes
Accepted

Examples of context sensitive syntactic constructs (statements)

Here are three context-sensitive syntaxes actually found in programming languages. I don't believe I've ever seen a language which has types, names and values distributed as per your example, but it ...
rici's user avatar
  • 12k
6 votes
Accepted

Is every language in PTime also context-sensitive?

It is an open question to separate $\mathsf{L}$ (that is, $\mathsf{DSPACE}(\log n)$) and $\mathsf{P}$ (what you call PTime), so in particular we have no example of a polytime language which requires ...
Yuval Filmus's user avatar
6 votes
Accepted

A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA. What happens if only one of the two stacks is linear bounded and the other is unlimited? I optimistically wrote a quick ...
Vor's user avatar
  • 12.5k
5 votes

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

You are asking two questions: how to construct a PDA for the language, and why this language is context-free while the same language with the condition $x \neq y$ replaced by the condition $x = y$, is ...
Yuval Filmus's user avatar
5 votes
Accepted

Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?

With three steps we are not forced to complete all the steps before continuing interacting with other context around the two initial letters. In fact, Révész himself answers this question, in his ...
Hendrik Jan's user avatar
  • 30.8k
5 votes

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

Intersections (and more generally, Boolean combinations) of context-free languages are included in the class LOGCFL, which is a quite weak subclass of P (on a low level of the NC hierarchy). Thus, it ...
Emil Jeřábek's user avatar
4 votes
Accepted

Membership problem for context sensitive languages PSPACE-complete

I'm assuming that the context-sensitive language is given to you as a context-sensitive grammar. Summarizing the Wikipedia article, here is how to show that the word problem for context-sensitive ...
Yuval Filmus's user avatar
4 votes
Accepted

context sensitive language finite or infinite

It's a standard theorem that it's undecidable whether a given context-sensitive grammar generates the empty language or not. From this, we can prove that it's undecidable whether a context-sensitive ...
D.W.'s user avatar
  • 160k
4 votes

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 ...
AProgrammer's user avatar
  • 3,069
4 votes

concatenation of context sensitive and context-free is context sensitive or not?

Suppose that $L$ is a context-sensitive language which is not context-free. Then $L\{\epsilon\}$ is not context-free (here $\epsilon$ is the empty word), while $L\emptyset$ is context-free.
Yuval Filmus's user avatar
4 votes
Accepted

Mildly context-sensitive grammar

You could have written a paper based on your discovery had you been researching this problem many years ago. In fact, the paper Terminal Context in Context-Sensitive Grammars by Ronald V. Book, 1972 ...
John L.'s user avatar
  • 39k
4 votes
Accepted

Are Context Sensitive Languages Turing Complete?

Context-sensitivity has nothing to do with the semantics of a language. A language could have an arbitrarily complicated grammar, and still not be able to do anything useful, perhaps because it has no ...
rici's user avatar
  • 12k
4 votes

How to give a context-sensitive grammar for a^nba^nba^nb?

One possible grammar is: \begin{align} S&\rightarrow Tb &(1)\\ T&\rightarrow AXY &(2)\\ T&\rightarrow ATXY &(3)\\ YX&\rightarrow YZ &(4)\\ YZ&\rightarrow WZ &(...
xskxzr's user avatar
  • 7,455
4 votes
Accepted

How can I show that this language is context sensitive?

In the same way that DFAs are the counterparts for regular expressions and PDAs are the counterparts for context free languages , the counterpart for context sensitive languages are LBAs (linear ...
Anwar's user avatar
  • 659
4 votes
Accepted

Can you diagonalize a language out of CSL?

This is accomplished by the nondeterministic space hierarchy theory, given that CSL is the same as $\mathsf{NSPACE}(n)$.
Yuval Filmus's user avatar
4 votes
Accepted

Are the set of all Bitcoin addresses a context-sensitive language?

Any answer I give you is likely to be unsatisfying and a little silly, both because we're squarely in theory-land here (and not the useful kind of theory, but theory that is irrelevant in practice), ...
D.W.'s user avatar
  • 160k
4 votes
Accepted

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$. An essentially noncontracting grammar would be: $S \to \varepsilon \...
Nathaniel's user avatar
  • 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 ...
chi's user avatar
  • 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$. ...
Raphael's user avatar
  • 72.5k
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 ...
Hendrik Jan's user avatar
  • 30.8k
3 votes
Accepted

Is {a^i b^j c^k | i≤j or (k=j≤i)} context sensitive?

There are two possible interpretations of the condition on $i,j,k$: $(i \leq j \lor j \leq i) \land j = k$. This condition is equivalent to just $j = k$, and so the language in question is $\{ a^i b^...
Yuval Filmus's user avatar
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 ...
Hans Hüttel's user avatar
  • 2,516
3 votes

How to give a context-sensitive grammar for a^nba^nba^nb?

Lemma 1: The non-contracting rule $XY\rightarrow YX$ can be rewritten as context-sensitive rules. Proof: We can replace $XY\rightarrow YX$ with the following four context-sensitive rules, $\quad XY\...
John L.'s user avatar
  • 39k
3 votes

What makes a common programming language non-context-sensitive but RE?

I think you are conflating syntax and semantics. A formal language is RE if it is possible to recursively enumerate all valid "sentences" (read "complete programs"). Validity here effectively means ...
rici's user avatar
  • 12k

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