Automata Theory
Automata theory is a branch of computer science that deals with abstract machines and computational processes. It explores the behavior and properties of these machines, such as finite automata, pushdown automata, and Turing machines, to understand the capabilities and limitations of computation. This theory forms the foundation for understanding formal languages, compilers, and the design of computer algorithms.
3 Key excerpts on "Automata Theory"
eBook - ePub- Apostolos Syropoulos, Theophanes Grammenos(Authors)
- 2020(Publication Date)
- Wiley(Publisher)
...8 Fuzzy Computation Computation is about calculating or enumerating mechanically. Typically, the word mechanically means that one builds a device and sets it in motion in order to perform the desired calculation or enumeration. Many and different real or conceptual devices capable of performing computations have been proposed. Most of them operate in a crisp environment and in a crisp manner. However, there are some devices that profit from the use of vagueness in their overall operation. These devices and the related theory are described in this chapter. The material presented in this chapter is based on [ 220, 274 ]. 8.1 Automata, Grammars, and Machines A finite automaton can be seen as a machine equipped with scanning head that can read the contents of sequence of cells, while the head can move in only one direction. At any moment, the machine is in a state. Initially, the scanning head is positioned on the leftmost cell, while a number of symbols are printed on consecutive cells starting with the leftmost cell. Also, the machine enters a default initial state. Each machine is associated with a number of transition rules. A transition rule has the general form, where and are states and is a symbol. The meaning of this rule is that if the automaton is in state, it will enter state only if the next symbol is. When the machine starts, it reads the first symbol and if there is a transition rule that includes this symbol and the current state, then the scanning head moves to the right and the machine enters a new state. If the machine enters the final state, then it accepts the input and terminates. The machine may suspend without completion when no transition rule applies. The alphabet of the machine consists of the symbols that the scanning head can recognize...
eBook - ePubIntroduction to Artificial Intelligence
Second, Enlarged Edition
- Philip C. Jackson(Author)
- 2013(Publication Date)
- Dover Publications(Publisher)
...This expectation is justified: The mathematical formalizations for parallel process so far developed are all essentially ways of describing complex machines that are made up of “interrelating” finite-state automata, Turing machines, or other types of information processors. Two such mathematical formalizations are discussed and a third is described. The first formalization is that of the theory of cellular automata (see Codd, 1968; Burks, 1970; A. R. Smith, 1969). At the outset it should be mentioned that the cells of a cellular automaton are not necessarily intended as models of their biological counterparts, the cells that comprise living organisms. The fact that this correlation does not necessarily exist is responsible for the other common name given to this type of machine, “tesselation automaton.” Briefly, a cellular automaton is a graph (note 8–1) whose nodes are finite-state machines (see Fig. 8–1a). The operation of a cellular automaton is determined by information passed between those nodes that are connected; the machine at each node receives the outputs of the machines at those nodes that connect to it. 1 Often, cellular automata are defined as being graphs of some simple nature, say that of an Abelian group (note 8–2), and in most cases the interconnections between nodes pass information bidirectionally (Fig. 8–1b). The important thing about this type of machine is that the underlying graph of a given cellular automaton is considered to be fixed, and is not capable of being altered by any of its nodes; this is the reason we can define the machine at each node by a simple finite-state function. A person observing a cellular automaton will consequently see its nodes changing state with time, each state affecting the others, etc. If the states used by the machines at the different nodes are the same, he may observe these states to be “flowing” throughout the graph in an interdependent manner...
eBook - ePubArtificial Intelligence
An Introduction
- Alan Garnham(Author)
- 2017(Publication Date)
- Routledge(Publisher)
...The theory specifies what computers can and cannot do and how much time and memory they need for the computations that they can perform. It therefore indicates the limitations of computational theories of the mind. The theory had its origins in several branches of mathematics. A number of mathematicians were independently searching for the smallest set of primitive operations needed to carry out any possible computation. When their proposals were worked out in detail, it was shown that they were equivalent. One approach to the problem of computability was Turing's (1936). Turing formulated his ideas in terms of an abstract computing device called a Turing machine. A Turing machine performs its calculations with the help of a tape divided into squares, each of which can have one symbol on it. The Turing machine's primitive operations are reading and writing symbols on the tape and shifting and tape one square to the left or right. It uses a finite vocabulary of symbols, but its tape can be infinitely long. A Turing machine has only a finite number of internal states. When it reads the symbol on a square its state may change, depending on what state it is currently in and what the symbol is. The structure of a Turing machine is very simple and so are the operations it performs. However, additional bits of 'machinery' - more tapes for example - do not increase the range of computations that a Turing machine can perform. They only increase its speed. Furthermore, these gains in efficiency are of no theoretical interest, since they speed up the machine's operation by only a constant factor. It is possible to describe a Universal Turing Machine, constructed on the same principles as other Turing machines. The Universal Turing Machine can mimic the operation of any other Turing machine. To simulate another machine it must be given a description of how that machine works. This description can be written on to its tape in standard Turing machine format...
