Automata theory has numerous applications in computer science, artificial intelligence, and communication theory. In computer science, automata theory is used to model Turing machines and other computing devices, and to study the problem of deciding whether a given program will halt on a certain input or not.
In artificial intelligence, automata theory is used to model intelligent agents, and to study the problem of deciding how a given agent will respond to specific situations. Now, let’s elaborate on what the automata theory is.
Automata Theory
The Automata theory is a hypothetical branch of computer science and mathematics that deals with abstract machines, known as Automata, and the computation problems that these machines can solve.
Automata are used to process formal language and its semantics. It takes a string as an input, goes through a finite set of states, and finally, it may enter a final state.
Representation of an Automata
Graphically, Automata are represented in the form of a directed graph. The nodes of the graph represent the states of an Automata.
Edges denote the transition from one state to another state. The final state is double-encircled. The initial state has an inward edge.
Types of Automata
There are four major types of automata:
- Finite Automata
- Pushdown Automata
- Linear-Bounded Automata
- Turing Machine
Finite Automata
It is the most straightforward machine used to recognize a language’s patterns. It has five tuples/components. These are Input language, finite set of states, initial state, final states, and transition function. Finite automata are characterized by two types:
- Deterministic finite automata (DFA)
- Nondeterministic finite automata (NFA)
Pushdown Automata
Unlike finite automata, pushdown automata have extra memory known as the stack, which enables pushdown automata to recognize context-free languages. A PDA has seven tuples/components. These are Input language, finite number of states, stack symbols, transition function, initial state (q0 ∈ Q), initial stack top, and final states.
Linear-Bounded Automata
Linear-bounded automata are similar to a Turing machine with non-deterministic logic, multi-track, and bounded finite-length tape. It has eight tuples/components. A finite set of states, tape alphabet, input language, the initial state, left end marker, right end marker, transition function, and the set of final states.
Turing Machines
It is a model with infinite tape divided into cells on which input is given. It accepts languages created by type 0 grammar. It has seven tuples/components. These are a finite set of states, tape language, input language, transition function, initial state, blank symbol, and the set of final states.
Basic Terminologies related to Automata
Following are some basic terminologies related to Automata Theory:
- Symbols
Symbols are individual identities/objects, such as letters, numbers, or images. For example, 1, a, %, and 0 are all symbols.
- Alphabets
A set of symbols form the alphabet. Alphabets are represented using ∑. For example, ∑ = {a, b} are alphabet.
- Strings
A finite combination of alphabets forms a string. For example, some strings use the alphabet
∑ = { a, b} can be aa, aba, abba, etc.
- Language
Language is a set of strings that can be infinite or finite. Language is denoted by L. For example, using the alphabet ∑ = {a, b} we can create a language
L = { x | x over ∑ ; |x| = 2 } = { aa, ab, ba, bb } -> Finite LanguageL = { x | x over ∑ ; number of a's in x are divisible by 2 } = { null, b, aa, bb, aab, aba, baa, bbb, ... } -> Infinite Language
