13.3 REWRITING SYSTEMS
The various grammars we have studied have a number of things in common with Post systems: They are all based on an alphabet in which strings are written and some rules by which one string can be obtained from another. Even a Turing machine can be viewed this way, since its instantaneous description is a string that completely defines its configuration. The program is then just a set of rules for producing one such string from a previous one. These observations can be formalized in the concept of a rewriting system. Generally, a rewriting system consists of an alphabet Σ and a set of rules or productions by which a string in Σ+ can produce another. What distinguishes one rewriting system from another is the nature of Σ ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
