This is about unrestricted grammars
S is the start symbol. Assume
0 are terminal symbols. Assume all other symbols are non-terminal.
Given a set of (non-trivial) grammar rules,
is it always possible to order them, such that,
all the symbols on the left:
- will be contained on the right in a previous rule
- or be the start symbol?
A grammar rule is trivial if discarding it does not change the language generated by it.
Example trivial rule:
S -> 1 S -> 0 A -> B
A is on the left of the third rule.
A is nowhere to be found in the other rules. Therefore the rule with
A can be removed without changing the grammar.
Another example trivial rule:
S -> 1 S -> 0 A -> B B -> A
A is found in another rule, but both rules containing
A together are trivial, since
B are not found in other rules.
S -> S T T -> S (T is on the left; T is in the previous rule) T -> 1 T -> 0
The second, third and fourth rule all start with
T, which is on the right hand side of a previous rule, therefore these rules are ordered as desired.