TUTORIAL-7
AUTOMATA
Finite automata are a useful model for many important kinds of hardware and
software.
1. Software for designing and checking the behaviour of digital circuits.
2. The “lexical analyzer” of a typical compiler i.e. the compiler component that
breaks the input text into logical units such as identifiers, keywords, and
punctuation.
3. Software for scanning large bodies of text such as collection of web pages, to
find occurrences of words, phrases or other patterns.
4. Software for verifying systems of all types that have a finite number of distinct
states, such as communications protocols or protocols for secure exchange of
information.
Two types of Finite automata :
Deterministic Finite Automata(DFA):
a) Single start state
b) Exactly one transition (change of state) for each input symbol
c) May have multiple accept state.
Nondeterministic Finite Automata(NFA):
d) May have multiple start state
e) May have more than one transition for each input symbol
f) May have multiple accept state.
Example: What should be the value of S,F,Q,∑,∂ for the following DFA.
0
3 1
5
0
1 0
2 4
0,1 1 1
Start state, S={3}
Set of accepting states, F={2,5}
Finite set of machine states, Q={1,2,3,4,5}
Input alphabet, ∑ = {0,1}
Transition function, ∂ is represented by the following transition table:
∂ 0 1
1 Φ Φ
2 {1} {1}
3 {2} {4}
4 {5} {1}
5 {5} {3}
Example: Draw the following DFA, given S={3}, F={2,4}, Q={1,2,3,4}, ∑ = {9, k,
$} and ∂ is represented by the following transition table.
∂ 9 K $
1 {1} {3} {2}
2 {4} {1} {3}
3 {4} {3} {1}
4 {2} {1} {2}
k 9
$
3
1
k
9 $ k
k $
9 2
4
9,
$
Example: What should be the value of S,F,Q, ∑,∂ for the following NFA.
a,b
1 a
2 3
b
b a b a,b
4 a 5 a,b 6
Start state, S={1,4}
Set of accepting states, F={2,3}
Finite set of machine states, Q={1,2,3,4,5,6}
Input alphabet, ∑ = {a,b}
Transition function, ∂ is represented by the following transition table:
∂ a b
1 {2} {2}
2 {3} Φ
3 {6} {6}
4 {5} {1}
5 {5,1} {2,3}
6 {5} {5}
Example: Draw the NFA for the following parameters.
S={3,4}, F={2,4}, Q={1,2,3,4}, ∑={9,k,+,5} and ∂ is represented by the following
transition table.
∂ 9 k + 5
1 {1} {2,3} {2} {1,2,3}
2 {1,4} Φ {1,3} Φ
3 {3,4} {3} Φ {3}
4 {2} Φ Φ Φ
9, k, 5 9,5
3 k,5 1
+, 9 k, + ,5
9
+
9 2
4
9
Example: For each of the following three automata, indicate in the table(true/false)
whether the machine accepts the input.
A1
a
1 2
b
a,b a,b
4
a 3
A2
a
1 2
b
a,b b
a a
3 b
4 a 5
b
A3
a,b 2 a 3
1
b b a,b
a b
4 5 6
a a,b
Input A1 A2 A3
abaa true false false
ababbaaa true false true
