Introduction to Theory of Automata
Automata Theory is a branch of computer science that deals with designing abstract computing models having a sequence of operations. With the help of that model, it will be easy to write algorithms and convert them into machines.
Automata − What is it?
The term “Automata” is derived from the Greek word “αὐτόματα” which means “self-acting”. An automaton (Automata in plural) is an abstract self-propelled computing device that follows a predetermined sequence of operations.
An automaton with a finite number of states is called a Finite Automata.
The formal definition of a Finite Automata
An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where −
- Q is a finite set of states.
- ∑ is a finite set of symbols, called the alphabet of the automaton.
- δ is the transition function.
- q0 is the initial state from where any input is processed (q0 ∈ Q).
- F is a set of final states/states of Q (F ⊆ Q).
Every Automaton fulfills the three basic requirements.
- It consists of some essential features as in real computers. It has a mechanism for reading input. The input is assumed to be a sequence of symbols over a given alphabet and is placed on an input tape(or written on an input file). The simpler automata can only read the input one symbol at a time from left to right but not change. Powerful versions can both read (from left to right or right to left) and change the input.
- The automaton can produce an output of some form. If the output in response to an input string is binary (say, accept or reject), then it is called an acceptor. If it produces an output sequence in response to an input sequence, then it is called a transducer (or automaton with output).
- The automaton may have temporary storage, consisting of an unlimited number of cells, each capable of holding a symbol from an alphabet (which may be different from the input alphabet). The automaton can both read and change the contents of the storage cells in the temporary storage. The accusing capability of this storage varies depending on the type of storage.
- The most important feature of the automaton is its control unit, which can be in any one of a finite number of interval states at any point. It can change the state in some defined manner determined by a transition function.
Diagrammatic representation of generic automation.
Related Terminologies
Alphabet
Definition − An alphabet is any finite set of symbols.
Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are alphabets.
String
Definition − A string is a finite sequence of symbols taken from ∑.
Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c,d}
Length of a String
Definition − It is the number of symbols present in a string. (Denoted by |S|).
Examples −If S=‘cabcad’, |S|= 6If |S|= 0, it is called an empty string (Denoted by λ or ε)
Kleene Star
Definition − The set ∑* is the infinite set of all possible strings of all possible lengths over ∑ including λ.
Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪…….
Example − If ∑ = {a, b}, ∑*= {λ, a, b, aa, ab, ba, bb,………..}
Kleene Closure/Plus
Definition − The set ∑+ is the infinite set of all possible strings of all possible lengths over ∑ excluding λ.
Representation − ∑+ = ∑0 ∪ ∑1 ∪ ∑2 ∪…….∑+ = ∑* − { λ }
Example − If ∑ = { a, b } , ∑+ ={ a, b, aa, ab, ba, bb,………..}
Language
Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.
Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, bb, ba, bb}.
