The state transition diagram for a string matching automaton for the pattern ababbabbababbababbabb over the alphabet is as follows:

The above transition diagram can be used to show the pattern ababbabbababbababbabb.

Here, first the simple transitions take place from the states 0, 1, 2,3….21 to traverse the entire string. Then, at each transition possibilities are detected to traverse the string.

String Matching Automaton for a Non-Overlappable Pattern

Normally a transition function is computed of a string matching automaton by the algorithm mentioned below. Consider the following algorithm computing transition function from a pattern:

COMPUTE_TRANSITION_FUNCTION (P,)

// m is the length of the string

1.

//Use of for loop which will examine character stored in string

2. for

//Use of for loop to perform operation on character

3. for every character a in

// +1 for x, +2 for subsequent repeat loop to decrement

4. k = min(m+1, q+2); // work backwards from q+1

5. repeat

6.

//condition for termination of repeat

7. until;

8. (q, a) = k;

//return the value of

9. return ;

Consider the state transition diagram:

This diagram shows the automaton of the string with 'm' number of states where p₀, p₁, p₂, …, p_m are the elements or characters of the string which when seen gets accepted and enters into the next state example on seeing p₀ the automaton is shifted from state 0 to state 1.For an non overlapping pattern string,

Consider P = p_0, p_1, p₂ ……... p_m

The specific feature of a nonoverlappable pattern is that its proper pre?x are not its su?x. This property is used for describing the destination of the outgoing arrow. For every pair, labeling of state q by a will be there.

As per the algorithm, the destination state k can be defined as:

1. When and: In this case, the value of k will be 1 more than the value of q. This can be given as:.

2. When: When the value of a is equal to p₁, then the value of k is set to 1. So, this condition will make the value of k equal to 1.

3. If any other condition arises: If both conditions given above are not satisfied, then the value of k is set to 0.

All the cases mentioned above can be shown as:

When case 1 is satisfied, then the value is obtained by using following equations:

The arrow will be from state q to state.

Now, denoting the value of k as:

It is clear from the above equation that is a su?x of a.

When the value of, then it is found that is a suffix of. For any of the non-overlappable pattern, this condition is impossible. So, the value of k will be either equal to 1 or less than 1. This means that the outgoing arrow having label a and from state q will either leads to state 1 or state 0. The outgoing arrow will lead to state 1 if condition given below will be satisfied:

The equation given above means that and it is a suffix of. In other words, the value of a is equal to p₁.

Construct the automata as follows:

Let be the longest prefix which is common in both P and . Create the automaton A for .

Construct an arrow from the state labelled k to the chain of states k+1, k+2, k+3……|P| and draw the necessary arrows so that the transition is .

For the pattern , show the transition from the state labelled to chain of states ,,…...

The transition for the pattern is ……(refer Theorem 32.4 of textbook)

The finite automata that determines the occurrences of either pattern can be shown below:

The transition from the first state to the intermediate states is shown in the following way:

The minimization of the number of the states in the automaton is done by eliminating the null states that is, which can be shown in the following way:

Thus, the states are expanded in the following way as: 11,12…… for the pattern P and as: 21,22…. for the pattern and on minimizing the null state each transition is shifted before by one step.

Consider the pattern which contains gap characters.

Let be the text.

Find the occurrence of the pattern in text .

Find the occurrence of pattern in text using the following steps:

• Divide pattern into substrings based on the gap character.

• Compare the sub pattern with text . If does not match with text , then the pattern does not match with text .

• If pattern is found in text , then compare pattern in the remaining part of text . If does not match with text , then the pattern does not match with text .

• Continue the process till all the patterns up to are matched with text . The process of comparison can be terminated at any point when does not match with text .

Construct finite automatons for each , that matches the sub pattern with text . The following is the generalized finite automaton that accepts the string if it matches with text :

Combine all the finite automatons that accept the sub pattern , with text . Also, the accepting state of, where , is no longer accepting the pattern, but has a single transition to .

The following is the generalized finite automaton to find the occurrence of pattern in text :

Each finite automaton requires at least matches and at most matches to verify that sub pattern matches with text .

Overall, the number of matches required will be equal to or in worst case.

However, .

Hence, the maximum number of matchings required is .

Therefore, the sequentially combined finite automaton is the required finite automaton that can find an occurrence of in a text in matching time, where .