Automata theory and formal languages : fundamental notions, theorems, and techniques / Alberto Pettorossi.
2022
QA76.9.H85
Linked e-resources
Linked Resource
Online Access
Concurrent users
Unlimited
Authorized users
Authorized users
Document Delivery Supplied
Can lend chapters, not whole ebooks
Details
Title
Automata theory and formal languages : fundamental notions, theorems, and techniques / Alberto Pettorossi.
ISBN
9783031119651 (electronic bk.)
3031119657 (electronic bk.)
3031119649
9783031119644
3031119657 (electronic bk.)
3031119649
9783031119644
Published
Cham : Springer, [2022]
Copyright
©2022
Language
English
Description
1 online resource (viii, 280 pages) : illustrations.
Other Standard Identifiers
10.1007/978-3-031-11965-1 doi
Call Number
QA76.9.H85
Dewey Decimal Classification
004.01/9
Summary
Knowledge of automata theory and formal languages is crucial for understanding human-computer interaction, as well as for understanding the various processes that take place when manipulating knowledge if that knowledge is, indeed, expressed as sentences written in a suitably formalized language. In particular, it is at the basis of the theory of parsing, which plays an important role in language translation, compiler construction, and knowledge manipulation in general. Presenting basic notions and fundamental results, this concise textbook is structured on the basis of a correspondence that exists between classes of automata and classes of languages. That correspondence is established by the fact that the recognition and the manipulation of sentences in a given class of languages can be done by an automaton in the corresponding class of automata. Four central chapters center on: finite automata and regular languages; pushdown automata and context-free languages; linear bounded automata and context-sensitive languages; and Turing machines and type 0 languages. The book also examines decidable and undecidable problems with emphasis on the case for context-free languages. Topics and features: Provides theorems, examples, and exercises to clarify automata-languages correspondences Presents some fundamental techniques for parsing both regular and context-free languages Classifies subclasses of decidable problems, avoiding focus on the theory of complexity Examines finite-automata minimalization and characterization of their behavior using regular expressions Illustrates how to derive grammars of context-free languages in Chomsky and Greibach normal forms Offers supplementary material on counter machines, stack automata, and abstract language families This highly useful, varied text/reference is suitable for undergraduate and graduate courses on automata theory and formal languages, and assumes no prior exposure to these topics nor any training in mathematics or logic. Alberto Pettorossi is professor of theoretical computer science at the University of Rome Tor Vergata, Rome, Italy.
Bibliography, etc. Note
Includes bibliographical references and index.
Access Note
Access limited to authorized users.
Source of Description
Description based on print version record.
Series
Undergraduate topics in computer science.
Available in Other Form
AUTOMATA THEORY AND FORMAL LANGUAGES.
Linked Resources
Online Access
Record Appears in
Online Resources > Ebooks
All Resources
All Resources
Table of Contents
1 Formal Grammars and Languages
2 Finite Automata and Regular Grammars
3 Pushdown Automata and Context-Free Grammars
4 Linear Bounded Automata and Context-Sensitive Grammars
5 Turing Machines and Type 0 Grammars
6 Decidability and Undecidability in Context-Free Languages
7 Supplementary Topics.
2 Finite Automata and Regular Grammars
3 Pushdown Automata and Context-Free Grammars
4 Linear Bounded Automata and Context-Sensitive Grammars
5 Turing Machines and Type 0 Grammars
6 Decidability and Undecidability in Context-Free Languages
7 Supplementary Topics.