Problem Solving in Automata, Languages, and Complexity

Problem Soluing in Automata, Languages, and Complexip Problem Solving in Automata, Languages, and Complexity. Ding-Zhu Du, Ker-I ...

Problem Solving in Automata, Languages, and Comytdexity Ding-Zhu Du Ker-I Ko A Wiley-Interscience Publication JOHN WILEY & S ...

Copyright2001 by John Wiley and Sons, Inc., New York. All rights reserved. No part of this publication may be reproduced, store ...

Preface Contents 1 Regular Languages 1 1.1 Strings and Languages^1 1.2 Regular Languages and Regular Expressions 8 1.3 Graph Rep ...

vi CONTENTS Asymptotic Growth Rate Time and Space Complexity Hierarchy Theorems Nondeterministic Turing Machines ...

Preface Over the past twenty years, automata and formal languages have become the standard introductory theory course in both th ...

Vlll... PREFACE formal languages, we limit ourselves to the basics in regular and context-free languages, and omit deterministic ...

Index ...

BP, see BIN PACKING BST,see BOTTLENECK STEINER Complete set, 251; see also NP- Conjunctive normal form (CNF), 342; Deterministic ...

Disjunctive normal form (DNF), 14, 358; see also Regular ex- pression Finite automata, see Deterministic fi- nite automata and N ...

Index set, see Set-index set and IP, see INTEGER PROGRAMMING context-free, see Context-free MCG, see MINIMUM CONNECTIVITY ...

NFA, see Nondeterministic finite au- tomata NTM, see Nondeterministic Turing approximation, see Approxima- Partial recursive fun ...

(^394) INDEX R. e. set, see Recursively enumerable set ...

3DM, see THREE-DIMENSIONAL TSP, see TRAVELING SALESMAN nondeterministic, see Nondeter- ...

4 Turing Machines 4.1 One-Tape Turing Machines 4.2 Examples of Turing Machines 4.3 Multi-Tape Turing Machines 4.4 Church-Turing ...

Regular Languages 1.1 Strings and Languages The basic object in automata and language theory is a string. A string is a finite s ...

2 REGULAR LANGUAGES The length of a string x, denoted by 1x1, is the number of symbols contained in the string. For example, [st ...

1.1 Strings and Languages Example 1.3 Solve the word equation X011 = 011X over the alphabet (0, 1); that is, find the set of str ...

REGULAR LANGUAGES Intersection A\B A-B Substrac tion Figure 1.1: Set operations. (c) Let A = {(Ol)n 1 n > - 0) and B = (01,01 ...

1.1 Strings and Languages 5 1x1 many O’s, and so x E (0, 10}lXl C {O,lO}*. Suppose ~xf contains n > 1 occurrences of 1 ‘s. Th ...