Formal Language: A Practical Introduction

✍ Scribed by Adam Brooks Webber

• Publisher: Franklin, Beedle & Assoc., Inc
• Year: 2008
• Tongue: English
• Leaves: 400
• Edition: 1
• Category: Library

✦ Synopsis

This book has two major goals. The first is to help you understand and appreciate the beautiful and enduring ideas of formal language. These ideas are the birthright of all computer scientists, and they will profoundly change the way you think about computation. They are not only among the most beautiful, but also among the most useful tools in computer science. They are used to solve problems in a wide variety of practical applications, and they are especially useful for defining programming languages and for building language systems. The second purpose of this book is to help you develop a facility with these useful tools. Our code examples are in Java, but they are not particularly Java-centric and should be accessible to any programmer. There is also a third major reason to study formal language, one that is not a primary focus of this book: to learn the techniques of mathematical proof. When you are learning about formal language, it can also be a good time to learn proof techniques, because the subject is full of theorems to practice on. But this book tries to make the beautiful and useful ideas for formal language accessible to students at all levels of mathematical interest and ability. To that end, although the book presents and discusses many simple proofs, it does not try to teach advanced proof techniques. Relatively few of the exercises pose challenging proof problems. Those planning graduate-level study of theoretical computer science would be well advised not to rely exclusively on this book for that kind of training.

✦ Table of Contents

• Introduction and Chapter 1: Fundamentals
• Chapter 2: Finite Automata
• Chapter 3: Closure Properties for Regular Languages
• Chapter 4: DFA Applications
• Chapter 5: Nondeterministic Finite Automata
• Chapter 6: NFA Applications
• Chapter 7: Regular Expressions
• Chapter 8: Regular Expression Applications
• Chapter 9: Advanced Topics in Regular Languages
• Chapter 10: Grammars
• Chapter 11: Non-Regular Languages
• Chapter 12: Context-Free Languages
• Chapter 13: Stack Machines
• Chapter 14: The Context-Free Frontier
• Chapter 15: Stack Machine Applications
• Chapter 16: Turing Machines
• Chapter 17: Computability
• Chapter 18: Uncomputability
• Chapter 19: Cost Models

✦ Subjects

Computer Science;AI & Machine Learning;Bioinformatics;Computer Simulation;Cybernetics;Human-Computer Interaction;Information Theory;Robotics;Systems Analysis & Design;Computers & Technology;Programming;APIs & Operating Environments;Algorithms;Apple Programming;Cross-platform Development;Functional;Game Programming;Graphics & Multimedia;Introductory & Beginning;Languages & Tools;Microsoft Programming;Mobile Apps;Parallel Programming;Software Design, Testing & Engineering;Web Programming;Computers