**String Matching with Finite Automata**

String Matching with Finite Automata is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.

- Many string-matching algorithms build a finite automaton that scans the text string
*T*for all occurrences of the pattern*P*. - We begin with the definition of a finite automaton. We then examine a special string-matching automaton and show how it can be used to find occurrences of a pattern in a text.
- Finally, we shall show how to construct the string-matching automaton for a given input pattern.

**Finite automata **

A *finite automaton **M *is a 5-tuple (*Q*, *q*0, *A*, Σ, *δ*), where

*Q*is a finite set of,*states**q*_{0 }Є*Q*is the,*start state**A C Q*is a distinguished set of,*accepting states*- Σ is a finite
,*input alphabet**δ*is a function from*Q*× Σ into*Q*, called theof*transition function**M*. - Moreover, The finite automaton begins 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 (“makes a transition”) from state q to state δ(q, a).
- Whenever its current state q is a member of A, the machine M said to have accepted the string read so far. An input that is not accepted said to be rejected.

The following Figure illustrates these definitions with a simple two-state automaton.

**String Matching Automata**

- There is a string-matching automaton for every pattern
*P*; this automaton must construct from the pattern in a preprocessing step before it can use to search the text string. - Also, In our example pattern
*P*= ababaca. - In order to properly search for the string, the program must define a
**suffix function (σ****)**which checks to see how much of what it is reading matches the search string at any given moment.

*σ*(*x*) = max {*k *: *P _{k }*

_{ }*x*}*P*= ababa

*P*_{1}=a

_{AP2}=ab

*P*_{3}=aba

*P*_{4}=abab

*σ* (ababaca)=aba {here aba is suffix of pattern P}

- We define the string-matching automaton that corresponds to a given pattern
*P*[1,…,*m*] as follows. - Also, The state set
*Q*is {0, 1 . . .*m*}. The start state*q*_{0}is state 0, and state*m*is the only accepting state. - The transition function
*δ*defined by the following equation, for any state*q*and character*a*:*δ (q, α) = σ(P*_{q}α)

**ALGORITHM FINITE-AUTOMATON-MATCHER(***T*, *δ*, *m*)

*T*,

*δ*,

*m*)

*n*←*length*[*T*]*q*← 0**for***i*← 1**to***n***do***q*←*δ*(*q*,*T*[*i*])**if***q =*=*m***then**print “Pattern occurs with shift”*i*–*m*

**ALGORITHM COMPUTE-TRANSITION-FUNCTION(***P*, Σ)

*P*, Σ)

*m*←*length*[*P*]**for***q*← 0 to*m***do****for**each character*α Є*Σ**do***k*← min(*m*+ 1,*q*+ 2)**repeat***k*←*k*– 1**until***P*⊐_{k }*P*_{q}*α**δ*(*q*,*α*) ←*k***return***δ*

This procedure computes *δ*(*q*, *α*) in a straightforward manner according to its definition.

Also, The nested loops beginning on lines 2 and 3 consider all states *q *and characters *α* and lines 4-7 set *δ*(*q*, *a*) to be the largest *k *such that *P _{k }*

*P*

_{q}*α*. The code starts with the largest conceivable value of

*k*, which is min (

*m*,

*q*+ 1), and decreases

*k*until

*P*

_{k}*P*

_{q}*α*.

Moreover, The time complexity for string matching algorithm.

**Related Terms**

ADA Algorithms, Travelling Salesman Problem, Naive String Matching Algorithm, Rabin-Karp Algorithm

## Leave a Reply