1
$\begingroup$

In the Chomsky hierarchy what is corresponding to a contracting grammar?

I can find references to non-contracting grammars (which can be transformed into context-sensitive grammars accordingly to what Wikipedia is saying: https://en.wikipedia.org/wiki/Noncontracting_grammar), but I don't know what would correspond to a contracting grammar

My guess would be unrestricted grammars (Type-0 in the Chomsky hierarchy) but I would like confirmation.

$\endgroup$

1 Answer 1

1
$\begingroup$

You are right. Unrestricted grammars (type-0) have productions $\alpha\to\beta$ with $\alpha$ containing at least one nonterminal.

For noncontracting (or monotonic) the condition $|\alpha|\le |\beta|$ is added.

I would not use the term "contracting" for what you try to express, though. That suggests that strings become shorter during derivations. Which is hard if one starts with a single symbol axiom. "not necessarily contracting" perhaps?

A similar problem occurs with automata terminology. A nondeterministic finite state automaton may very well be deterministic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.