In string rewriting system, does rewriting 'consume' the string? For instance, suppose $101$ is written down and there's a rule $1x1 \rightarrow 11x11,$ we can apply this rule to write down $11011,$ but do we have to cross off $101$?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
No, we are interested in the transitive closure of $\rightarrow$, i.e. what can be derived from given premises. There is no erasure necessarily involved, only non-deterministic choice. For example if we have the rules $1x1 \rightarrow 11x11$ and $x0x \rightarrow x$ then we have $101 \rightarrow 11011$ by the first rule and $101 \rightarrow 1$ by the second and all three strings $(101, 11011, 1)$ are deductions of the string rewriting system, so there is not really any sense in which the first is crossed off.