String Matching with Finite Automata

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, q₀,A,∑_δ), where

• Q is a finite set of states,
• q₀ ∈ 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 q₀ 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:

q₀ is the initial state.