SkipCaptcha
265
edits
Changes
→Level 3: regular grammar: mention constraint on left-hand side
===Level 3: regular grammar===
===Level 3: regular grammar===
The transformation rules for regular grammars are required to be very simple. The right-hand side of any rule must be one of:
The transformation rules for regular grammars are required to be very simple.
* [nothing].
*Only a single non-terminal item can appear on the left-hand side of a rule.
* a terminal item.
*The right-hand side of any rule must be one of:
* a terminal item followed by a non-terminal item.
**[nothing].
Note that instead of a terminal item we could have a non-terminal item whose transformation rule immediately resolves to a single terminal item.
**a terminal item.
**a terminal item followed by a non-terminal item.
Note that instead of a terminal item we could have a non-terminal item whose transformation rule immediately resolves to a single terminal item, or to one of several terminal items.
====Example====
====Example====