O'Reilly logo

Introduction to Formal Languages, Automata Theory and Computation by Kamala Krithivasan, R Rama

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required