Alexander Meduna - Böcker

Formal Languages and Computation: Models and Their Applications gives a clear, comprehensive introduction to formal language theory and its applications in computer science. It covers all rudimental topics concerning formal languages and their models, especially grammars and automata, and sketches the basic ideas underlying the theory of computation, including computability, decidability, and computational complexity. Emphasizing the relationship between theory and application, the book describes many real-world applications, including computer science engineering techniques for language processing and their implementation.Covers the theory of formal languages and their models, including all essential concepts and propertiesExplains how language models underlie language processors Pays a special attention to programming language analyzers, such as scanners and parsers, based on four language models—regular expressions, finite automata, context-free grammars, and pushdown automataDiscusses the mathematical notion of a Turing machine as a universally accepted formalization of the intuitive notion of a procedureReviews the general theory of computation, particularly computability and decidability Considers problem-deciding algorithms in terms of their computational complexity measured according to time and space requirementsPoints out that some problems are decidable in principle, but they are, in fact, intractable problems for absurdly high computational requirements of the algorithms that decide them In short, this book represents a theoretically oriented treatment of formal languages and their models with a focus on their applications. It introduces all formalisms concerning them with enough rigors to make all results quite clear and valid. Every complicated mathematic

Jumping Computation: Updating Automata and Grammars for Discontinuous Information Processing is primarily a theoretically oriented treatment of jumping automata and grammars, covering all essential theoretical topics concerning them, including their power, properties, and transformations. From a practical viewpoint, it describes various concepts, methods, algorithms, techniques, case studies and applications based upon these automata and grammars.In today’s computerized world, the scientific development and study of computation, referred to as the theory of computation, plays a crucial role. One important branch, language theory, investigates how to define and study languages and their models, which formalize algorithms according to which their computation is executed. These language-defining models are classified into two basic categories: automata, which define languages by recognizing their words, and grammars, which generate them. Introduced many decades ago, these rules reflect classical sequential computation. However, today’s computational methods frequently process information in a fundamentally different way, frequently “jumping” over large portions of the information as a whole. This book adapts classical models to formalize and study this kind of computation properly. Simply put, during their language-defining process, these adapted versions, called jumping automata and grammars, jump across the words they work on.The book selects important models and summarizes key results about them in a compact and uniform way. It relates each model to a particular form of modern computation, such as sequential, semi-parallel and totally parallel computation, and explains how the model in question properly reflects and formalizes the corresponding form of computation, thus allowing us to obtain a systematized body of mathematically precise knowledge concerning the jumping computation. The book pays a special attention to power, closure properties, and transformations, and also describes many algorithms that modify jumping grammars and automata so they satisfy some prescribed properties without changing the defined language. The book will be of great interest to anyone researching the theory of computation across the fields of computer science, mathematics, engineering, logic and linguistics.

Jumping Computation: Updating Automata and Grammars for Discontinuous Information Processing is primarily a theoretically oriented treatment of jumping automata and grammars, covering all essential theoretical topics concerning them, including their power, properties, and transformations. From a practical viewpoint, it describes various concepts, methods, algorithms, techniques, case studies and applications based upon these automata and grammars.In today’s computerized world, the scientific development and study of computation, referred to as the theory of computation, plays a crucial role. One important branch, language theory, investigates how to define and study languages and their models, which formalize algorithms according to which their computation is executed. These language-defining models are classified into two basic categories: automata, which define languages by recognizing their words, and grammars, which generate them. Introduced many decades ago, these rules reflect classical sequential computation. However, today’s computational methods frequently process information in a fundamentally different way, frequently “jumping” over large portions of the information as a whole. This book adapts classical models to formalize and study this kind of computation properly. Simply put, during their language-defining process, these adapted versions, called jumping automata and grammars, jump across the words they work on.The book selects important models and summarizes key results about them in a compact and uniform way. It relates each model to a particular form of modern computation, such as sequential, semi-parallel and totally parallel computation, and explains how the model in question properly reflects and formalizes the corresponding form of computation, thus allowing us to obtain a systematized body of mathematically precise knowledge concerning the jumping computation. The book pays a special attention to power, closure properties, and transformations, and also describes many algorithms that modify jumping grammars and automata so they satisfy some prescribed properties without changing the defined language. The book will be of great interest to anyone researching the theory of computation across the fields of computer science, mathematics, engineering, logic and linguistics.

The essential guide to grammars with context conditions This advanced computer science book systematically and compactly summarizes the current knowledge about grammars with context conditions-an important area of formal language theory. According to the types of context conditions, this self-contained reference classifies them into grammars with context conditions placed on the domains of grammatical derivations, the use of grammatical productions, and the neighborhood of the rewritten symbols. The focus is on grammatical generative power, important properties, simplification, reduction, implementation, and applications, most of which are related to microbiology. The text features:* Up-to-date coverage of grammatical concepts based on context conditions* Self-contained explanations without assumption of any previous knowledge* Clear definitions and exact proofs preceded by intuitive explanations* Numerous easy-to-implement grammatical transformations* Realistic applications* Relation to mathematics, linguistics, and biology* Additional material and information about the book available on accompanying Web site (see preface for details) Practitioners and advanced students in theoretical computer science and related areas- including mathematics, linguistics, and molecular biology-will find Grammars with Context Conditions and Their Applications an essential reference for this cutting-edge area of formal language theory.

Formal Languages and Computation: Models and Their Applications gives a clear, comprehensive introduction to formal language theory and its applications in computer science. It covers all rudimental topics concerning formal languages and their models, especially grammars and automata, and sketches the basic ideas underlying the theory of computation, including computability, decidability, and computational complexity. Emphasizing the relationship between theory and application, the book describes many real-world applications, including computer science engineering techniques for language processing and their implementation.Covers the theory of formal languages and their models, including all essential concepts and propertiesExplains how language models underlie language processors Pays a special attention to programming language analyzers, such as scanners and parsers, based on four language models—regular expressions, finite automata, context-free grammars, and pushdown automataDiscusses the mathematical notion of a Turing machine as a universally accepted formalization of the intuitive notion of a procedureReviews the general theory of computation, particularly computability and decidability Considers problem-deciding algorithms in terms of their computational complexity measured according to time and space requirementsPoints out that some problems are decidable in principle, but they are, in fact, intractable problems for absurdly high computational requirements of the algorithms that decide them In short, this book represents a theoretically oriented treatment of formal languages and their models with a focus on their applications. It introduces all formalisms concerning them with enough rigors to make all results quite clear and valid. Every complicated mathematic

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.

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.

The theory of computation is used to address challenges arising in many computer science areas such as artificial intelligence, language processors, compiler writing, information and coding systems, programming language design, computer architecture and more. To grasp topics concerning this theory readers need to familiarize themselves with its computational and language models, based on concepts of discrete mathematics including sets, relations, functions, graphs and logic.This handbook introduces with rigor the important concepts of this kind and uses them to cover the most important mathematical models for languages and computation, such as various classical as well as modern automata and grammars. It explains their use in such crucially significant topics of computation theory as computability, decidability, and computational complexity. The authors pay special attention to the implementation of all these mathematical concepts and models and explains clearly how to encode them in computational practice. All computer programs are written in C#.

Automata and Languages presents a step-by-step development of the theory of automata, languages and computation. Intended to be used as the basis of an introductory course to this theory at both junior and senior levels, the text is organized in such a way as to allow the design of various courses based on selected material. Areas featured in the book include:- *basic models of computation *formal languages and their properties *computability, decidability and complexity *a discussion of the modern trends in the theory of automata and formal languages *design of programming languages, including the development of a new programming language *compiler design, including the construction of a complete compiler Alexander Meduna uses clear definitions, easy-to-follow proofs and helpful examples to make formerly obscure concepts easy to understand. He also includes challenging exercises and programming projects to enhance the reader's comprehension, and, to put the theory firmly into a 'real world' context, he presents lots of realistic illustrations and applications in practical computer science.

This textbook gives a systematized and compact summary, providing the most essential types of modern models for languages and computation together with their properties and applications.

This textbook gives a systematized and compact summary, providing the most essential types of modern models for languages and computation together with their properties and applications.