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. Front Matter....Pages i-xx Front Matter....Pages 1-1 Chapter 1 Introduction....Pages 3-7 Chapter 2 Mathematical Background....Pages 9-13 Chapter 3 Rudiments of Formal Language Theory....Pages 15-36 Front Matter....Pages 37-37 Chapter 4 Context-Based Grammatical Regulation....Pages 39-154 Chapter 5 Rule-Based Grammatical Regulation....Pages 155-187 Front Matter....Pages 189-189 Chapter 6 One-Sided Versions of Random Context Grammars....Pages 191-279 Chapter 7 On Erasing Rules and Their Elimination....Pages 281-328 Chapter 8 Extension of Languages Resulting from Regulated Grammars....Pages 329-349 Chapter 9 Sequential Rewriting Over Word Monoids....Pages 351-361 Front Matter....Pages 363-363 Chapter 10 Regulated ET0L Grammars....Pages 365-429 Chapter 11 Uniform Regulated Rewriting in Parallel....Pages 431-444 Chapter 12 Parallel Rewriting Over Word Monoids....Pages 445-453 Front Matter....Pages 455-455 Chapter 13 Regulated Multigenerative Grammar Systems....Pages 457-489 Chapter 14 Controlled Pure Grammar Systems....Pages 491-505 Front Matter....Pages 507-507 Chapter 15 Self-Regulating Automata....Pages 509-530 Chapter 16 Automata Regulated by Control Languages....Pages 531-563 Front Matter....Pages 565-565 Chapter 17 Jumping Finite Automata....Pages 567-585 Chapter 18 Deep Pushdown Automata....Pages 587-601 Front Matter....Pages 603-603 Chapter 19 Applications: Overview....Pages 605-613 Chapter 20 Case Studies....Pages 615-650 Front Matter....Pages 651-651 Chapter 21 Concluding Remarks....Pages 653-668 Chapter 22 Summary....Pages 669-678 Back Matter....Pages 679-694