## Problem Solving in Automata, Languages, and ComplexityAutomata and natural language theory are topics lying at the heart of computer science. Both are linked to computational complexity and together, these disciplines help define the parameters of what constitutes a computer, the structure of programs, which problems are solvable by computers, and a range of other crucial aspects of the practice of computer science. In this important volume, two respected authors/editors in the field offer accessible, practice-oriented coverage of these issues with an emphasis on refining core problem solving skills. |

### What people are saying - Write a review

User Review - Flag as inappropriate

Better examples than most books about automata, including Hopcroft's.

### Contents

1 | |

2 Finite Automata | 23 |

3 ContextFree Languages | 89 |

4 Turing Machines | 159 |

5 Computability Theory | 225 |

6 Computational Complexity | 281 |

7 NPCompleteness | 323 |

387 | |

389 | |

### Other editions - View all

Problem Solving in Automata, Languages, and Complexity Ding-Zhu Du,Ker-I Ko No preview available - 2004 |

Problem Solving in Automata, Languages, and Complexity Ding-Zhu Du,Ker-I Ko No preview available - 2001 |

### Common terms and phrases

accepts the input algorithm alphabet Assume binary strings cell Church-Turing Thesis computation path condition construct an NFA contains context-free grammar context-free language crossing sequences deﬁne deﬁnition denote DFA’s DTM’s edge encode exactly Example Exercise exists ﬁnal ﬁnd ﬁrst ﬁve ﬁxed function f given grammar G graph G halts induction inﬁnite initial conﬁguration input symbol input tape instance instruction integer length move multi-tape NFA’s nondeterministic nonterminal symbol Note NP-complete one-tape DTM output pair parse tree partial recursive function partition polynomial polynomial-time preﬁx primitive recursive function problem Proof prove PSPACE pumping lemma r.e. set reduction regular expression regular language rules satisﬁes Section sentential form set of binary Show shown in Figure simulate Solution stack symbols Steiner subset substring Suppose tape head tape symbols Theorem transition diagram transition function Turing machine Turing-computable vertex cover vertices