To Support Customers in Easily and Affordably Obtaining Titles in Electronic Format
IGI Global is Now Offering a **50% Discount** on ALL E-Books and E-Journals Ordered Directly Through IGI Global’s Online Bookstore

Additionally, Enjoy a 20% Discount on all Other Products and FormatsBrowse Titles

Additionally, Enjoy a 20% Discount on all Other Products and FormatsBrowse Titles

Subrata Paul (Vignan Institute of Technology and Management, India) and Anirban Mitra (Vignan Institute of Technology and Management, India)

Copyright: © 2020
|Pages: 21

DOI: 10.4018/978-1-7998-2460-2.ch068

Chapter Preview

TopAutomata theory is an exciting, theoretical branch of computer science. It established its roots during the 20th Century, as mathematicians began developing - both theoretically and literally - machines which imitated certain features of man, completing calculations more quickly and reliably. The word automaton itself, closely related to the word “automation”, denotes automatic processes carrying out the production of specific processes. Simply stated, it deals with the logic of computation with respect to simple machines, referred to as automata. Through automata, computer scientists are able to understand how machines compute functions and solve problems and more importantly, what it means for a function to be defined as computable or for a question to be described as decidable (Yan, 1998).

The major objective of automata theory is to develop methods by which computer scientists can describe and analyse the dynamic behaviour of discrete systems, in which signals are sampled periodically. The behaviour of these discrete systems is determined by the way that the system is constructed from storage and combinational elements (Chakraborty, Saxena & Katti, 2011). Characteristics of such machines include inputs, outputs and states. Inputs are assumed to be sequences of symbols selected from a finite set *I* of input signals. Namely, set *I* is the set {*x*_{1},*x*_{2},*x*_{3},…,*x _{k}*} where

There are four major families of automaton. These are finite state machine, pushdown automata, linear bounded automata, and Turing machine. The families of automata can be interpreted in a hierarchal form, where the finite state machine is the simplest automata and the Turing machine is the most complex. A Turing machine is a finite state machine yet the inverse is not true (Amadek & Trnkova, 1990). The following Figure 1 depicts the families of automaton.

TopA finite automaton is the mathematical model of some machine whose state may change in time, the set of possible states being finite. Its behaviour is the succession of its states throughout time. Its characteristically features are the set of states, *Q*, and the rules for their changes. The number of states being finite, there is no question of a continuous course, so the time-scale will be *N*. Changes are ruled by the function *δ* mapping state of automaton at time *t*, denoted (*a,t*), on state at time (*t*+1)

The behaviour of the automaton is studied from an initial state *a*, it is the sequence:

As just described, isolated and independent from any outer surrounding, automaton presents very little interest; indeed, if *k* is the number of states in *Q*, two out of the (*k* + 1) states from time 0 to time *k* must be the same (Lane, 1971).

Providing an input and an output to automaton, where input alphabets are the set of possible inputs (denoted by *X)*. The state of the automaton *a* at certain time will depend not only on its previous state but also on its present input at the preceding time which can be expressed as,<(*a, t* + 1) >= δ(< *a, t* >, *x*(*t*))where *x(t)* denotes input at time t. The set of possible outputs will be called the output alphabet, noted Y, the output at a certain time depending only on the state:

Search this Book:

Reset

Copyright © 1988-2020, IGI Global - All Rights Reserved