2
$\begingroup$

I was reading an article at

What does "context" in "context-free grammar" refer to?

The production

zA -> xy

is described as being an "unrestricted" production. In what way is it "unrestricted"?

I even visited https://en.wikipedia.org/wiki/Unrestricted_grammar

which talks about unrestricted grammar as the one that is comprised of productions which have no restriction on LHS or RHS. On this note, I assume that an unrestricted production is the one with no restriction on LHS or RHS.

What restrictions are being talked about and how is the production free from such restrictions?

$\endgroup$

1 Answer 1

2
$\begingroup$

A single rule can not be "unrestricted".

The whole set of rules is $(T \cup N)^+ \to (T \cup N)^*$. So the class of unrestricted grammars may use any rule from this set.

Restricted classes of grammars are only allowed to use a strict subset of all rles, e.g.

  • right-regular grammars are restricted to $N \to T^*N^{\{0,1\}}$, and
  • context-free grammars to $N \to (T \cup N)^*$.

By going through the Chomsky hierarchy, you will note that the rule

$\qquad zA \to xy$

is not admitted in any but the type-0 grammars; try to see why it's not a "context-sensitive rule". That does not mean it is only ever allowed in the unrestricted class -- just that it's not in any on this list. There are many more classes.

$\endgroup$

Your Answer

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

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