2
$\begingroup$

This is about unrestricted grammars

Assume S is the start symbol. Assume 1 and 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

Now A is found in another rule, but both rules containing A together are trivial, since A and B are not found in other rules.

Example grammar:

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.

$\endgroup$
1
  • 2
    $\begingroup$ By the way, it is undecidable that given a grammar, whether a rule can be discarded. Even assume the grammar is context-free, it is still undecidable. $\endgroup$
    – John L.
    Jul 18 at 0:27

2 Answers 2

7
$\begingroup$

Yes.


Given a grammar $G$ that contains no trivial production rules, here is a simple algorithm that lists all grammar rules such that all the symbols on the left of a rule except $S$ are contained on the right of a previous rule.

  1. Let $ordered\_rules$ be an empty list of rules.
  2. Let $available\_symbols$ be a set that contains $S$. Besides $S$, $~available\_symbols$ will always contain all the symbols on the right of a rule in $ordered\_rules$.
  3. As long as there is a rule in $G$ but not in $ordered\_rules$, find a rule $r$ such that all the symbols on the left of $r$ are in $available\_symbols$.
    1. Add all the symbols that are on the right of $r$ to $available\_symbols$.
    2. Append $r$ to $ordered\_rules$
  4. Return $ordered\_rules$.

Why does the algorithm above work?

Suppose there is a rule in $G$ but not in $ordered\_rules$.

Since no rule in $G$ can be discarded, there is a word $w$ that is generated with at least one application of a rule not in $ordered\_rules$. Consider the very first moment that a rule not in $ordered\_rules$, say $r$ is applied in a derivation of $w$. By the choice of that moment, all the symbols on the left of $r$ must have been either $S$ or on the right of rules in $ordered\_rules$, i.e., they are in $available\_symbols$.

Hence, step 3 of the algorithm will loop until all rules are in $ordered\_rules$.

$\endgroup$
1
  • $\begingroup$ If "all the symbols on the left" in the question is replaced by "all the non-terminals on the left", the answer to the question is still yes. Just replace every appearance of "all the symbols" in the answer above with "all the non-terminals". $\endgroup$
    – John L.
    Jul 18 at 1:50
5
$\begingroup$

Yes. Use the following greedy algorithm:

  • Mark the start symbol $S$
  • While there exists an unselected transition such that (*) all the nonterminals in $\alpha$ are marked:
    • Select an arbitrary transition $\alpha \to \beta$ that satisfies (*).
    • Mark all nonterminals in $\beta$.

The order in which transitions are selected satisfies your requirement by construction. To see that unselected transitions are trivial notice that it is not possible to generate all nonterminals on their left-hand-side from $S$.

$\endgroup$

Your Answer

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

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