LEADER 04740nam 22006615 450 001 9910586636603321 005 20251202145437.0 010 $a9783031119651$b(electronic bk.) 010 $z9783031119644 024 7 $a10.1007/978-3-031-11965-1 035 $a(MiAaPQ)EBC7073259 035 $a(Au-PeEL)EBL7073259 035 $a(CKB)24429523600041 035 $a(PPN)264192001 035 $a(BIP)85351144 035 $a(BIP)84660512 035 $a(DE-He213)978-3-031-11965-1 035 $a(EXLCZ)9924429523600041 100 $a20220812d2022 u| 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aAutomata Theory and Formal Languages $eFundamental Notions, Theorems, and Techniques /$fby Alberto Pettorossi 205 $a1st ed. 2022. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2022. 215 $a1 online resource (287 pages) 225 1 $aUndergraduate Topics in Computer Science,$x2197-1781 311 08$aPrint version: Pettorossi, Alberto Automata Theory and Formal Languages Cham : Springer International Publishing AG,c2022 9783031119644 327 $a1 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. 330 $aKnowledge 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; linearbounded 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. 410 0$aUndergraduate Topics in Computer Science,$x2197-1781 606 $aMachine theory 606 $aComputer science 606 $aComputable functions 606 $aRecursion theory 606 $aFormal Languages and Automata Theory 606 $aComputer Science Logic and Foundations of Programming 606 $aComputability and Recursion Theory 606 $aTheory and Algorithms for Application Domains 615 0$aMachine theory. 615 0$aComputer science. 615 0$aComputable functions. 615 0$aRecursion theory. 615 14$aFormal Languages and Automata Theory. 615 24$aComputer Science Logic and Foundations of Programming. 615 24$aComputability and Recursion Theory. 615 24$aTheory and Algorithms for Application Domains. 676 $a004.019 676 $a004.019 700 $aPettorossi$b Alberto$017835 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 912 $a9910586636603321 996 $aAutomata Theory and formal languages$9712989 997 $aUNINA