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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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}(...
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 ...
user avatar
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 ...
user avatar
  • 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$...
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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
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$$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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 ...
user avatar
  • 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 &(...
user avatar
  • 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 ...
user avatar
  • 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)$.
user avatar
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^...
user avatar
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$...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 2,448

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