14
My favourite example of a context-sensitive language (CSL) is SAT. The Landweber-Kuroda Theorem says that CSL = NSPACE$[n]$. Any SAT instance has a linear-size certificate, so SAT is a CSL. See my question Context-sensitive grammar for SAT? for references and discussion.
Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE.
...
9
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 one wants to allow the empty string, a special case is made and the rule $S\to\lambda$ is allowed with ugly side conditions ($S$ cannot appear in a right-hand ...
9
The first closure property, closure under intersection, is a DIY proof if you choose the right model for the context-sensitive languages. By defining them with the help of linear-bounded automata you can run two of these automata successively to test (nondeterministically) for acceptance of the intersection.
Second, closure under complement, is hard! It ...
9
Yes, context-sensitive grammars (CSG) are powerful enough to make undefined/undeclared/unbound variables check, but unfortunately we don't know any efficient algorithm to parse strings of CSG.
A real example of a context-sensitive language is the C programming language. A feature like declare variables first and then use them later make C-language a context-...
9
First, all context-sensitive languages are decidable, since they can be accepted by a LBA (as you said), and a Turing machine is more powerful than a LBA.
However, you were asking about something else. Can there be LBA that cycles? The answer is yes. You gave an example. However, you can modify every LBA $M$ to a Turing machine $M'$ that accepts the same ...
8
Yes, I would believe this to be possible, but no I am not willing to explicitly construct that context-sensitive grammar. I will explain my answer, by splitting the question in two different parts.
(1) What would the non-toy example be? It should reflect declaration of variables. My proposal of such a language, abstracted from real programming would be ...
8
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 definition I could think of is this: A language
class $\mathcal{C}$ has a pumping lemma if there is a decidable ternary
predicate $P(\cdot,\cdot,\cdot)$ where $P(g,w,d)...
8
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}(n) = \mathsf{NSPACE}(n)$, and so $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ implies the well-known conjecture $\mathsf{L} \neq \mathsf{NL}$.
The conjecture $...
6
Indeed, there is a simple trick that allows you to add extra information at a certain position: just replace a letter adjacent to the position and mark it with the information, and the original letter.
In your example, have a nonterminal $M$ for the middle, but as it can not be deleted, it also counts as a normal letter. Thus we have two copies $M_a$ and $...
6
The context that is needed tells us the types of known variables. Suppose We want to infer the type of
if b or 2 = x then a else b
To make sense of this we need to
Check that the type of b is bool
That the type of x is numeric
That a and b have the same type.
To answer these three questions, we look up information about variables in a typing context, ...
6
First, they describe noncontracting grammars, and give an example: the one you are quoting.
Next, they write: equivalently, we can use a different restriction on grammars, and describe the context-sensitive grammars.
Chomsky proved the equivalence in 1963.
6
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 could certainly exist, and I'm sure there are even less readable syntaxes which are possible. The following are at least somewhat readable:
Syntactic whitespace,...
6
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 yourself that there are only countable many of them; Why can they be enumerated?),
Let $x_1, x_2, \ldots,$ be enumeration of $\Sigma^*$ (i.e., $x_1=\epsilon$, ...
6
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$ be the pumping lemma constant.
I can choose $z = 0^{2n}10^{2n}10^{n} $. Clearly $|z| \geq n$.
Now let $z = uvwxy$ be any decomposition of $z$ such that $|vwx|...
6
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 models. Usually a context-sensitive grammar is allowed one extra product to optionally produce the empty string. Alternatively, there is an equivalence between ...
6
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 superlogarithmic space.
5
Intuitively you want to generate three intermediate symbols at a time, and allow the symbols to sort themselves. Let $S$ be the start symbol. The generation rules are:
$$S \rightarrow S A_1 A_2 A_3$$
$$S \rightarrow S B_1 B_2 B_3$$
The sorting rules are as follows: For symbols $X_i,Y_i \in \{A_1,A_2,A_3,B_1,B_2,B_3\}$ such that $j < i$ add the rule:
$$...
5
Your grammar will generate:
$S\rightarrow 0S12\rightarrow 00S1212\rightarrow 001212$ which is not in the required language.
5
$repeat(\cdot)$ is an operator on languages. It takes as an input a language $L$, and outputs a language defined by $\{ xx \mid x \in L\}$. That is, for any word $x\in L$ the string $xx$ will be in the output language $repeat(L)$.
A Few examples:
$L=\{ 0,00, 11\}$ => $repeat(L) = \{ 00,0000,1111\}$
$L=\{ \}$ => $repeat(L) = \{ \}$
$L=\Sigma^*=\{\...
5
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 not. I will only answer the second, since for the first question there are known algorithms.
The reason that your language is context-free is that we can ...
5
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 Introduction to Formal Languages at archive.org, with the following example.
Note that three rules like AB → A'B, A'B → A'D, and A'D → CD are
not enough to ...
5
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 comment that the LBA equivalence holds also in this case ... but ...
It's easy to see/prove that a 2-stack PDA with a linear bound only on one stack can simulate a ...
4
This follows from closure properties of CSL: it's closed against intersection and $\epsilon$-free homomorphism, but not against (general) homomorphism.
Thus, $h(L_1 \cap L_2)$ is always context-sensitive if $h$ is $\epsilon$-free.
If $h$ is not, $h(L_1 \cap L_2)$ may not be. As an example, take $L_1$ and $h$ from the proof that CSL is not closed against ...
4
We have the following MSO characterization of regular nested word languages:
Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two unary predicates call and return, linear successor and the matching relation ↝.
The recommended reference on Nested Words and Visibly Pushdown Languages treats ...
4
Saying that CF grammars are properly contained in CS grammars is not quite
correct, at least according to some authors (Hopcroft-Ullman
1979, page 223). Their reason is that the CS languages cannot contain the empty
word $\epsilon$, at least according to a strict definition of what a
CS grammar is: the right-hand side must be at least as long as the
left-...
4
Designing context-sensitive grammars (with productions $\alpha X \gamma \to \alpha \beta \gamma$ with $\beta \neq \varepsilon$) is no fun at all. It is slightly more convenient to construct monotone grammars (with productions $\alpha \to \beta$ with $|\alpha| \le |\beta|$). There is a standard construction from one to the other.
But even then it is full of ...
4
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 grammar is finite or infinite. Let $L$ be a context-sensitive language. By the standard closure properties for CSL's, if $L$ is context-sensitive, then so is $...
4
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.
4
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 &(5)\\
WZ&\rightarrow WY &(6)\\
WY &\rightarrow XY &(7)\\
AX &\rightarrow AbA_X &(8)\\
A_XX&\rightarrow A_XA_X &(9)\\
A_XY&\...
3
Hint: The language is not context-free. So you will need to employ a type of grammar that is more powerful. Context-sensitive grammars can do the job.
If you need guidance in how to build a context-sensitive grammar for such a language, you might want check a context-sensitive grammar for $a^nb^nc^n$.
Only top voted, non community-wiki answers of a minimum length are eligible
