10
votes
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
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 ...
- 361
8
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.4k
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}(...
- 270k
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 ...
- 270k
7
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 ...
- 27.6k
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$...
- 507
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 ...
- 11.3k
6
votes
Accepted
How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)
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-...
- 4,676
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 ...
- 270k
5
votes
How to generate a context sensitive grammar for www
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$$
...
- 567
5
votes
Accepted
What is language of repeat(L) = {ww | w ∊ L}?
$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 ...
- 20.4k
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 ...
- 270k
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 ...
- 27.6k
5
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 ...
- 12.2k
4
votes
Accepted
Does applying a homomorphism to the intersection of two CSLs yield RE languages?
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-...
- 70.9k
4
votes
Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$
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 ...
- 27.6k
4
votes
Accepted
Have non-regular language classes of infinite words been studied?
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 ...
- 5,322
4
votes
Accepted
From context-free to context-sensitive
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 ...
- 19.1k
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.♦
- 141k
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.
- 270k
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 ...
- 11.3k
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 &(...
- 7,250
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 ...
- 629
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)$.
- 270k
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^...
- 270k
3
votes
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
3
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 ...
- 3,004
3
votes
Creating a grammar from the language
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-...
- 6,519
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,448
Only top scored, non community-wiki answers of a minimum length are eligible