Automata, Computability and Complexity

"Combining classic theory with unique applications, this crisp narrative is supported by abundant examples and clarifies key concepts by introducing important uses of techniques in real systems. Broad-ranging coverage allows instructors to easily customize course material to fit their unique requirements. Salient Features Focus on applications - Demonstrates why studying theory will make them better system designers and builders Classic theory combined with new applications - Includes fresh discussion of applications such as computational biology Review of background mathematical concepts- Addresses students' varying backgrounds in discrete mathematics and logic Clear notation and naming conventions - Uses consistent, easily understandable formats to indicate definitions and name variables and objects Thorough coverage of automata theory: - Features topics such as use of the closure theorems for regular and context-free languages, ambiguity in context-free grammars, parsing, functions on languages, and decision procedures for regular and context-free languages - Also includes coverage of top-down and bottom-up parsers, stochastic automata, context-sensitive languages, the Chomsky hierarchy, and recursive functions"