The string-matching automaton is a very useful tool which is used in string matching algorithm. It examines every character in the text exactly once and reports all the valid shifts in O (n) time. The goal of string matching is to find the location of specific text pattern within the larger body of text (a sentence, a paragraph, a book, etc.)
Finite Automata:
A finite automaton M is a 5-tuple (Q, q0,A,∑δ), where
- Q is a finite set of states,
- q0 ∈ Q is the start state,
- A ⊆ Q is a notable set of accepting states,
- ∑ is a finite input alphabet,
- δ is a function from Q x ∑ into Q called the transition function of M.
The finite automaton starts in state q0 and reads the characters of its input string one at a time. If the automaton is in state q and reads input character a, it moves from state q to state δ (q, a). Whenever its current state q is a member of A, the machine M has accepted the string read so far. An input that is not allowed is rejected.
A finite automaton M induces a function ∅ called the called the final-state function, from ∑* to Q such that ∅(w) is the state M ends up in after scanning the string w. Thus, M accepts a string w if and only if ∅(w) ∈ A.
The function f is defined as
∅ (∈)=q0 ∅ (wa) = δ ((∅ (w), a) for w ∈ ∑*,a∈ ∑)
FINITE- AUTOMATON-MATCHER (T,δ, m),
1. n ← length [T]
2. q ← 0
3. for i ← 1 to n
4. do q ← δ (q, T[i])
5. If q =m
6. then s←i-m
7. print "Pattern occurs with shift s" s
The primary loop structure of FINITE- AUTOMATON-MATCHER implies that its running time on a text string of length n is O (n).
Computing the Transition Function: The following procedure computes the transition function δ from given pattern P [1......m]
COMPUTE-TRANSITION-FUNCTION (P, ∑)
1. m ← length [P]
2. for q ← 0 to m
3. do for each character a ∈ ∑*
4. do k ← min (m+1, q+2)
5. repeat k←k-1
6. Until
7. δ(q,a)←k
8. Return δ
Example: Suppose a finite automaton which accepts even number of a's where ∑ = {a, b, c}
Solution:
q0 is the initial state.
0 Comments