Regulated Grammars and Automata

This is the first book to offer key theoretical topics and terminology concerning regulated grammars and automata. They are the most important language-defining devices that work under controls represented by additional mathematical mechanisms. Key topics include formal language theory, grammatical regulation, grammar systems, erasing rules, parallelism, word monoids, regulated and unregulated automata and control languages. The book explores how the information utilized in computer science is most often represented by formal languages defined by appropriate formal devices. It provides both algorithms and a variety of real-world applications, allowing readers to understand both theoretical concepts and fundamentals. There is a special focus on applications to scientific fields including biology, linguistics and informatics. This book concludes with case studies and future trends for the field. Regulated Grammars and Automata is designed as a reference for researchers and professionals working in computer science and mathematics who deal with language processors. Advanced-level students in computer science and mathematics will also find this book a valuable resource as a secondary textbook or reference.

Table of Contents

Part I Introduction and Terminology
Chapter 1 Introduction
Chapter 2 Mathematical Background
Chapter 3 Rudiments of Formal Language Theory

Part II Regulated Grammars: Fundamentals
Chapter 4 Context-Based Grammatical Regulation
Chapter 5 Rule-Based Grammatical Regulation

Part III Regulated Grammars: Special Topics
Chapter 6 One-Sided Versions of Random Context Grammars
Chapter 7 On Erasing Rules and Their Elimination
Chapter 8 Extension of Languages Resulting from Regulated Grammars
Chapter 9 Sequential Rewriting Over Word Monoids

Part IV Regulated Grammars: Parallelism
Chapter 10 Regulated ET0L Grammars
Chapter 11 Uniform Regulated Rewriting in Parallel
Chapter 12 Parallel Rewriting Over Word Monoids

Part V Regulated Grammar Systems
Chapter 13 Regulated Multigenerative Grammar Systems
Chapter 14 Controlled Pure Grammar Systems

Part VI Regulated Automata
Chapter 15 Self-Regulating Automata
Chapter 16 Automata Regulated by Control Languages

Part VII Related Unregulated Automata
Chapter 17 Jumping Finite Automata
Chapter 18 Deep Pushdown Automata

Part VIII Applications
Chapter 19 Applications: Overview
Chapter 20 Case Studies

Part IX Conclusion
Chapter 21 Concluding Remarks
Chapter 22 Summary