No label defined (Q4486016)

The book presents some aspects of formal language theory combining algebraic and algorithmic approach with decidability and applications within and outside of computer science. The book is divided into four parts. The first part, `Introductory notions', contains chapters 1 and 2, and deals with concepts related to sets, relations, functions, operations and algebras, sequences, graphs, cardinality, words, languages, substitutions and morphisms, matrices and languages, polynomials functions. The second part, `Regular and Context-Free Languages', contains chapters 3 to 6, and presents problems related to regular languages (finite automata, transition systems, transducers, regular expressions, syntactic monoids, closure properties, pumping lemma), rewriting systems and grammars (Chomsky hierarchy, (Semi-)Thue systems, properties of type-2 grammars, regular languages and type-3 grammars), context-free languages (derivation trees, fixed-point theorems, normal forms, pumping lemmas, closure properties, ambiguity, Parikh theorem, Chomsky-Schutzenberger theorem), pushdown automata (nondeterministic and deterministic cases) The third part, `Algorithmic aspects', contains chapters 7 to 9, and presents partial recursive functions (primitive recursive and partial recursive functions, primitive recursive languages, predicates, numerical primitive recursive functions, bounded minimalization, extensions), recursively enumerable languages (Markov algorithms, Curch's thesis, deterministic and nondeterministic Turing machines, multitape Turing machines, Post correspondence problem, Rice's theorem), context-sensitive languages, (linear bounded automata, normal forms for context sensitive grammars, closure properties for the families of languages). The last part, `Applications', contains chapters 10 and 11, and presents codes (unique decipherability, Kraft-McMillan inequality, Huffman's code, data compression), biological applications (L-systems, DNA computing). The presentation is an useful textbook for an undergraduate as well as for a (post)graduate course in computer science containing various classical topics and more than 600 exercises. On the other hand, by the wealth of results presented, it may be used by scientists too. The applications presented refer to computer science topics (operating systems and text processing, computer networks, data compression) or biology (L-systems and DNA computing).