Информатика и вычислительная техника
  • формат pdf
  • размер 5.93 МБ
  • добавлен 27 декабря 2011 г.
Lawson M.V. Finite Automata
Издательство CRC Press, 2004, -326 pp.

The theory of finite automata is the mathematical theory of a simple class of algorithms that are important in computer science. Algorithms are recipes that tell us how to solve problems; the rules we lea in school for adding, subtracting, multiplying and dividing numbers are good examples of algorithms. Although algorithms have always been important in mathematics, mathematicians did not spell out precisely what they were until the early decades of the twentieth century, when they started to ask questions about the nature of mathematical proof. Perhaps motivated in part by the mechanical devices that were used to help in arithmetical calculations, mathematicians wanted to know whether there were mechanical ways of proving theorems. By mechanical, they did not intend to build real machines that could prove theorems; rather they wanted to know whether it was possible in principle to prove theorems mechanically. In mathematical terms, they wanted to know whether there was an algorithm for proving the theorems of mathematics. The answer to this question obviously depended on what was meant by the word ‘algorithm.’ Numerous definitions were suggested by different mathematicians from various perspectives and, remarkably, they all proved to be equivalent. By the end of the 1930s, mathematicians had a precise definition of what an algorithm was, and using this definition they were able to show that there were problems that could not be solved by algorithmic means. It was perhaps no accident that, as mathematicans were laying the foundations of the theory of algorithms, engineers were constructing machines that could implement algorithms as programs. Algorithms and programs are just two sides of the same coin. Mathematicians were initially interested in the dividing line between what was and what was not algorithmic. But simply knowing that a problem could be solved by means of an algorithm was not the end of the story. Certainly, this implied you could write a program to solve the problem, but did not imply your program would run quickly or efficiently. For this reason, two approaches to classifying algorithms were developed. The first classified them according to their running times and is known as complexity theory, whereas the second classified them according to the types of memory used in implementing them.

Introduction to finite automata
Recognisable languages
Non-deterministic automata
?-automata
Kleene’s Theorem
Local languages
Minimal automata
The transition monoid
The syntactic monoid
Algebraic language theory
Star-free languages
Varieties of languages
A Discrete mathematics
Читать онлайн
Похожие разделы
Смотрите также

Aiserman M., Gusev L., Rozonoer L., Smirnova l., Tal A. Logic, Automata, and Algorithms

  • формат pdf
  • размер 5.3 МБ
  • добавлен 03 января 2012 г.
Издательство Academic Press, 1971, -444 pp. This book deals with the general theory of finite automata and sequential machines, a subject of great current theoretical and practical importance and one likely to have an even greater impact in the future. In writing this text, we had in mind a wide audience. We naturally hoped i t would be useful to specialists in switching or digital computer theory and design. Such persons are already familiar wi...

D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction

  • формат pdf
  • размер 13.64 МБ
  • добавлен 03 января 2012 г.
Издательство Springer, 2005, -268 pp. An automata network is a collection of automata connected together according to a directed graph D. The vertices of D are considered as automata and the edges indicate the existence of communication links. Thus D has no parallel edges. Each automaton can change its state at discrete time steps as a local transition function of the states and a global input, and synchronous action of the local state transitio...

Ginzburg A. Algebraic Theory of Automata

  • формат djvu
  • размер 1.89 МБ
  • добавлен 01 ноября 2011 г.
Издательство Academic Press, 1968, -173 pp. This monograph is intended to provide a graduate student and a newcomer to the field with ideas, methods, and results of algebraic theory of automata ; nevertheless, people working in the area may find the book useful, too, especially the chapters about regular expressions and the decomposition theory of Krohn and Rhodes. The book can serve as a text for a one-semester course in Automata Theory. The...

Kobrinskii N.E., Trakhtenbrot B.A. Introduction to the Theory of Finite Automata

  • формат djvu
  • размер 2.09 МБ
  • добавлен 01 ноября 2011 г.
Издательство North Holland, 1963, -342 pp. In recent years, intensive work has been in progress at a number of centres to develop and apply various automatic digital systems for information processing. Such systems form the basis of digital computers, various control devices operating to a specified algorithm, and of models which simulate the activity of a living organism (termed robots). These automata take the form of independent special-purpo...

Mikolajczak B. Algebraic and structural automata theory

  • формат djvu
  • размер 2.16 МБ
  • добавлен 01 ноября 2011 г.
Издательство North Holland, 1991, -424 pp. The subject of research in automata theory is a design of mathematical models describing methods of information transformation in digital systems. Automata theory is especially concerned with abstract models of systems working by means of discrete signals, known as digital signals. Special emphasis has been put on digital computers, digital systems of control for technological processes, and digital sys...

Pin J.E. (ed.) Formal Properties of Finite Automata and Applications

  • формат djvu
  • размер 2.38 МБ
  • добавлен 01 ноября 2011 г.
Издательство Springer, 1989, -268 pp. The subject of the sixteenth School is the theory of finite automata and its applications. However two important parts of this theory are not treated in this volume, because they were already the subject of two earlier Spring Schools : "Automata on infinite words" (Spring School 1984) and "Automata Networks" (Spring School 1986). The proceedings have been divided into three sections. The first section is de...

Salomaa A., Wood D., Yu S. (eds.) A Half-Century of Automata Theory. Сelebration and Inspiration

  • формат djvu
  • размер 608.85 КБ
  • добавлен 01 ноября 2011 г.
Издательство World Scientific Publishing, 2001, -164 pp. In the past half century, automata theory has been established as one of the most important foundations of computer science, and its applications have spread to almost all areas of computer science. Research in automata theory and related areas has also reached a crucial point where researchers are searching for new directions. To celebrate the achievements in automata theory in the past h...

Shallit J. A Second Course in Formal Languages and Automata Theory

  • формат pdf
  • размер 1.36 МБ
  • добавлен 14 октября 2011 г.
Издательство Cambridge University Press, 2008, -254 pp. Intended for graduate students and advanced undergraduates in computer science, A Second Course in Formal Languages and Automata Theory treats topics in the theory of computation not usually covered in a first course. After a review of basic concepts, the book covers combinatorics on words, regular languages, context-free languages, parsing and recognition, Turing machines, and other langua...

Tao R. Finite Automata and Application to Cryptography

  • формат pdf
  • размер 3.31 МБ
  • добавлен 28 сентября 2011 г.
Издательство Tsinghua/Springer, 2008, -441 pp. The important summarizing work of RENJI TAO appears now in book form. It is a great pleasure for me to see this happen, especially because I have known Professor Tao as one of the very early contributors to public-key cryptography. The research community has missed a book such as the present one now published by Tsinghua University Press and Springer. The book will be of special interest for student...

Taubner D. Finite Representations of CCS and TCSP Programs by Automata and Petri Nets

  • формат djvu
  • размер 1.31 МБ
  • добавлен 01 ноября 2011 г.
Издательство Springer, 1989, -167 pp. There are two main approaches to a theory of concurrent distributed computations: the theory of Petri nets and the Milner/Hoare theory of CCS/CSP. They are based on different philosophies and emerged from two different classical notions of computability. The Petri net approach developed (in the early 60s) from the ideas around Turing machines and automata; it has concurrency and causality as its basic concep...