Home » DAA String Matching with Finite Automata

DAA String Matching with Finite Automata

by Online Tutorials Library

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, 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}

String Matching with Finite Automata

Solution:

q0 is the initial state.

String Matching with Finite Automata

You may also like