Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?

  • 8
    $\begingroup$ I think you mean classes of languages containing all context-free languages but not containing all context-sensitive languages. Do en.wikipedia.org/wiki/Chomsky_hierarchy and en.wikipedia.org/wiki/Mildly_context_sensitive_language answer your question? $\endgroup$ – Colin McQuillan Sep 17 '12 at 11:20
  • 2
    $\begingroup$ To be fair, he might mean classes of grammars. That said, if he means what you say, he might find cs.stackexchange.com/q/110/69 interesting. $\endgroup$ – Patrick87 Sep 18 '12 at 20:19
  • 2
    $\begingroup$ Your level numbers don't make sense in the context of the usual type 0 to 3 classification. Please clarify which you mean (i.e. context-sensitive, context-free,...). $\endgroup$ – Raphael Sep 18 '12 at 22:06

I know I'm pretty late, but oh well.

There's a class of grammars known as indexed grammars (describing indexed languages, which are a proper subset of CS languages and a superset of CF languages). The rules look very much like the ones in a CF grammar, but every LHS nonterminal has an associated stack of index symbols, and when rewriting that nonterminal, the stack can be manipulated by other nonterminals in the RHS. For example:

$A[\sigma] \rightarrow B[\sigma x] C[\sigma y]$

which means "rewrite nonterminal A to nonterminals B and C, copy the stack and push x to B's stack and y to C's stack" or

$A[\sigma x] \rightarrow B[\sigma]$

meaning "if there's an A with x on top of its stack, rewrite it to B and pop that x off the B's stack".

Some examples of indexed languages are $\left\{ a^n b^n c^n d^n | n \geq 1 \right\}$ or $\left\{ www | w \in \left\{ a, b \right\}^+ \right\}$.

As for the automaton, indexed languages are exactly the class of formal languages recognizable by a nondeterministic nested-stack automaton, which is basically a NPDA in which some elements of the stack may be other stacks.

Concerning practical use, wikipedia says that indexed grammars sometimes find use as affordably processable descriptors of natural languages.

Edit: As Raphael mentioned, indexed languages | grammars are closely related to mildly context-sensitive languages.

There's a class of grammars similar to indexed grammars called linear indexed grammars. While in an IG, every nonterminal in the RHS recieves a copy of the LHS's stack, LIGs require that at most one nonterminal in the RHS recieves the stack. Given that any LIG can be transformed into an equivalent IG, they're strictly less powerful and it has been shown that the set of languages they generate is equivalent to the set of mildly context-sensitive languages.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy