scientific article; zbMATH DE number 1462097

Authors Dan A. Simovici, Richard L. Tenney

Publication date 21 June 2000

automata Chomsky hierarchy closure properties decidability finite automata formal languages grammars linear bounded automata partial recursive function pushdown automata regular and context-free languages regular expressions Turing machines

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45)

Review text

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).

Recommendations

Cited in

(12)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4486016)