Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
Accepted

Context-sensitive grammar for function calls

As far as I can determine by looking for examples with Google, the answer seems to be: it can be done, but please don't. Regarding context-sensitive rules, Chomsky wrote: Rules of this kind are quite ...
reinierpost's user avatar
  • 5,694
3 votes
Accepted

Language of equal numbers of as, bs, cs in any order not context-sensitive?

It seems the author of the book is a little careless at this point. His definition of context-sensitive is that "the right-hand side of a rule must never be shorter than the left-hand side" ...
Hendrik Jan's user avatar
  • 30.7k
2 votes
Accepted

Is { a^nb^na^n} a context-sensitive language?

The grammar: $S\to aS'Ba\mid aba \mid\varepsilon$ $S'\to aS'Ba\mid aba$ (so that only the start symbol can generate the empty word) $aB \to Ba$ (to move the inner $a$'s to the right) $bB \to bb$ (to ...
Nathaniel's user avatar
  • 15.7k
2 votes

Valid rules in CSG

What Hopcroft and Ullman call a context-sensitive grammar is nowadays called a noncontracting grammar; see page 223. The two types of grammar are equivalent in power.
Yuval Filmus's user avatar
1 vote

How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

I think the language is indeed context-sensitive. Here is a non-contracting grammar generating it. $S \to A' \mid B' \mid aS' \mid \varepsilon$ $A' \to aA' \mid a$ (in the case there is no $b$'s, ...
Nathaniel's user avatar
  • 15.7k
1 vote

Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

The shortest non-contracting grammar we could come up with is: \begin{align*} S&\rightarrow a\ |\ LR\\ L&\rightarrow LD\ |\ D\\ Da&\rightarrow a^2D\\ DR&\rightarrow aR\ |\ a^2 \end{...
Athlici's user avatar
  • 11

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