Automata theory (also known as Theory Of Computation) is a theoretical branch of
Computer Science and Mathematics, which mainly deals with the logic of computation with
respect to simple machines, referred to as automata.
Automata* enables the scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyse the dynamic behavior of discrete systems.
Automata originated from the word “Automaton” which is closely related to “Automation”.
Now, let’s understand the basic terminologies, which are important and frequently used in Theory of Computation.
Symbol: Symbol is the smallest building block, which can be any alphabet, letter or any picture.
Alphabets (Σ): Alphabets are set of symbols, which are always finite.
String: String is a finite sequence of symbols from some alphabet. String is generally denoted as w and length of a string is denoted as |w|.
0101010000011111
aaabbbcaac
Note:
A={}
Empty string is the string with
zero occurrence of symbols,
represented as ε.
Number of Strings (of length 2)
that can be generated over the alphabet {a, b} -
- -
1. a a
2. a b
3. b a
4. b b
Length of String |w| = 2
Number of Strings = 4
Language: A language is a set of strings, chosen from some Σ* or we can say- ‘A language is a subset of Σ* ‘. A language which can be formed over ‘ Σ ‘ can be Finite or Infinite.
L -> set finite ,infinite
Finite state automata
Finite Automata(FA) is the simplest machine to recognize patterns.
A Finite Automata consists of the following :
Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.
Formal specification of machine is
{ Q, Σ, q, F, δ }.
FA is characterized into two types:
1) Deterministic Finite Automata (DFA)
DFA consists of 5 tuples {Q, Σ, q, F, δ}.
Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.
In a DFA, for a particular input character, the machine goes to one state only. A transition function is defined on every state for every input symbol. Also in DFA null (or ε) move is not allowed, i.e., DFA cannot change state without any input character.
For example, below DFA with Σ = {0, 1} accepts all strings ending with 0.
One important thing to note is, there can be many possible DFAs for a pattern. A DFA with minimum number of states is generally preferred.
2) Nondeterministic Finite Automata(NFA)
NFA is similar to DFA except following additional features:
1. Null (or ε) move is allowed i.e., it can move forward without reading symbols.
2. Ability to transmit to any number of states for a particular input.
However, these above features don’t add any power to NFA. If we compare both in terms of power, both are equivalent.
Due to above additional features, NFA has a different transition function, rest is same as DFA.
δ: Transition Function
δ: Q X (Σ U ε ) --> 2 ^ Q.
As you can see in transition function is for any input including null (or ε), NFA can go to any state number of states.
For example, below is a NFA for above problem
One important thing to note is, in NFA, if any path for an input string leads to a final state, then the input string accepted. For example, in above NFA, there are multiple paths for input string “00”. Since, one of the paths leads to a final state, “00” is accepted by above NFA.
Some Important Points:
1. Every DFA is NFA but not vice versa.Justification:
Since all the tuples in DFA and NFA are the same except for one of the tuples, which is Transition Function (δ)
In case of DFA
δ : Q X Σ --> Q
In case of NFA
δ : Q X Σ --> 2Q
Now if you observe you’ll find out Q X Σ –> Q is part of Q X Σ –> 2Q.
In the RHS side, Q is the subset of 2Q which indicates Q is contained in 2Q or Q is a part of 2Q, however, the reverse isn’t true. So mathematically, we can conclude that every DFA is NFA but not vice-versa. Yet there is a way to convert an NFA to DFA, so there exists an equivalent DFA for every NFA.
2. Both NFA and DFA have the same power and each NFA can be translated into a DFA.
3. There can be multiple final states in both DFA and NFA.
4. NFA is more of a theoretical concept.
5. DFA is used in Lexical Analysis in Compiler.
Conclusion:
For alphabet {a, b} with length n, number of
strings can be generated = 2n.
Note – If the number of Σ’s is represented by |Σ|, then number of strings of length n, possible over Σ is |Σ|n.
Powers of ‘ Σ ‘ :
Say Σ = {a,b} then
Σ0 = Set of all strings over Σ of length 0. {ε}
Σ1 = Set of all strings over Σ of length 1. {a, b}
Σ2 = Set of all strings over Σ of length 2. {aa, ab, ba, bb}
i.e. |Σ2|= 4 and Similarly, |Σ3| = 8
Cardinality : Number of elements in a set, which is basically |Σ|n.
Σ* is a Universal Set.
Σ* = Σ0 U Σ1 U Σ2 ..........
= {ε} U {a, b} U {aa, ab, ba, bb}
= ............. //infinite language.
