Introduction to Formal Languages, Automata Theory and Computation

Chapter 13. Recent Trends and Applications

Regulated Re-writing

In a given grammar, re-writing can take place at a step of a derivation by the usage of any applicable rule in any desired place. That is, if A is a nonterminal occurring in any sentential form say αAβ, the rules being A → γ, A → δ, then any of these two rules are applicable for the occurrence of A in αAβ. Hence, one encounters nondeterminism in its application. One way of naturally restricting the nondeterminism is by regulating devices, which can select only certain derivations as correct in such a way that the obtained language has certain useful properties. For example, a very simple and natural control on regular rules may yield a non-regular language.

While defining the four types ...