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 ...

Get Introduction to Formal Languages, Automata Theory and Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.