Automata and Computability: A Programmer's Perspective

ISBN-13: 9780367656546 / Angielski / Miękka / 2020 / 328 str.

Ganesh Gopalakrishnan

Opis

This class-tested textbook provides a comprehensive and accessible introduction to the theory of automata and computation. It incorporates modern/handy ideas, such as derivative-based parsing and a Lambda reducer showing the universality of Lambda calculus.

Spis treści

I Foundations

1 What Machines Think

2 Defining Languages: Patterns in Sets of Strings

3 Kleene Star: Basic Method of defining Repetitious Patterns

II Machines

4 Basics of DFAs

5 Designing DFA

6 Operations on DFA

7 Nondeterministic Finite Automata

8 Regular Expressions and NFA

9 NFA to RE conversion

10 Derivative-based Regular Expression Matching

11 Context-Free Languages and Grammars

12 Pushdown Automata

13 Turing Machines

III Concepts

14 Interplay Between Formal Languages

15 Post Correspondence, and Other Undecidability Proofs

16 NP-Completeness

17 Binary Decision Diagrams as Minimal DFA

18 Computability using Lambdas

O autorze

Ganesh Gopalakrishnan is a professor in the Computer Science Department at the University of Utah.