Finite Automata Algorithm for Pattern Searching Using Python

What is Finite Automata?

The Finite Automata is a machine used to recognize different patterns. Finite Automata is used to characterize the regular language. It is also used in analyzing Natural Language expression. The finite automata or finite state automata have five main elements or tuples, including:

Input
Output
States of Automata
State Relation
Output Relation

The automata machine consists of various states and rules, allowing it to move from one state to another. This depends on the input symbol. Any input string can be accepted or rejected on the basis of these states and rules.

It is mainly a machine that accepts the input string and then converts the initial state according to the input string.

Pattern Matching is a vital task in computer science, where we search for a pattern string in the text string. The Finite Automata Algorithm is used to search patterns. The text-matching automaton is an extremely valuable tool in the string-matching algorithm.

String matching algorithms create a finite automaton that searches the text string for all occurrences of the pattern string.

Problem Statement of Finite Automata Algorithm for Pattern Matching

We are provided an input string str[0….. m - 1] and a pattern string ptn[0…. n - 1]. We need to write a function to search the pattern from the input string, which has the parameters (char ptn[ ], char str[ ]). This function will print the number of times the pattern string ptn[ ] occurs in the input string str[ ]. We can assume that the length of the input string is greater than that of the pattern string (m > n).

Let's understand the problem statement with a few examples.

Example 1:

Input:

str [ ] = " HELLO, TODAY IS A GOOD DAY."
ptn [ ] = "IS"

Output:

The Pattern "IS" is found at index 12.

Example 2:

Input:

str [ ] = "AABBAADAABBAACCAA"
ptn [ ] = "AABBAA"

Output:

The Pattern "AABBAA" is found at index 0 and 7.

Finite Automata Algorithm for Pattern Searching Using Python

The Approach of Finite Automata Algorithm for Pattern Searching

We will make the finite automata, which accepts the input string to search for the pattern in the input string.
Then, it will analyze every character of the input string only one time to search the pattern.

Time Complexity of Finite Automata Algorithm for Pattern Matching

The Time complexity of this algorithm is O (M³ |∑|), where M is the Automata Machine and ∑ is the input string.

The automata machine is defined by tuple M = {Q, ∑, q, A, δ }

Here,

Q = set of states in finite automata

∑ = set of input symbols

q₀ = initial state

A = set of strings

δ = Transition Function from Q x ∑

The finite automata starts with q₀, the initial state. Then, it starts reading the input string one by one. If the automation is in the state q and reads an input a, it moves from one state to another state δ (q, a). The Automata Machine M accepts the input string when the current state q is a member of A (set of strings); otherwise, it rejects the input.

Algorithm to Search Pattern in the Input String

Function Finite Automata (S, R)
State S < = 0
for len < = 1 to n
S < = δ (S, xi)
If S == ele then
Match Found
end
end

Why Finite Automata?

The Finite Automata algorithm for searching patterns in the text string is very efficient and useful as it searches every character exactly once. It takes less time to search the patterns. It takes more processing time, i.e., the time to create the finite automation machine.

Let's make and understand finite automata for a pattern string ABABACA.

The number of states in the finite automata is N + 1, where N is the pattern length. The basic goal of building a Finite Automaton is to determine the future state from the present state for each possible character.

The pattern string ptn [0… x - 1] can determine the next state, where x is the state. The goal is to find the length of the largest prefix of the provided pattern, which is also a suffix of ptn[0.. x-1] k. The length value determines the next state.

Now, we will implement the finite automata algorithm to search patterns in the text string.

Program 1: Program to implement the finite automata algorithm to search patterns in the text string in Python.

Code:

characters = 256
# Calculating next state
def NextState(ptn, M, S, x):
    if S < M and x == ord(ptn[S]):
        return S + 1
    i = 0
    for n in range(S , 0, - 1):
        if ord(ptn[n - 1]) == x:
            while(i < n - 1):
                if ptn != ptn[S - n + 1 + i]:
                    break
                i += 1
            if i == n - 1:
                return n
    return 0

def compute(ptn, M):
    # function representing Finite Automata
    global characters
    TF = [[0 for i in range(characters)]\

        for _ in range(M + 1)]
    for S in range(M + 1):
        for x in range(characters):
            z = NextState(ptn, M, S, x)
            TF[S][x] = z
    return TF

def search(ptn, str):
    # Prints all occurrences of pattern in the input text
    global characters
    M = len(ptn)
    N = len(txt)
    TF = compute(ptn, M)
    S = 0

    for i in range(N):
        S = TF[S][ord(str[i])]

        if S == M:
            print("Pattern found at index: { }".\
                format(i - M + 1))

def main():
    str = "AABABBBAABABAAAMMAABABAAB"
    ptn = "AABAB"

    search(str, txt)

if __name__ == '__main__':

    main()

Output:

Pattern found at index: 0
Pattern found at index: 7
Pattern found at index: 17

Explanation:

In this code, the compute( ) function is used to make the finite automata. This Algorithm takes O (l³ x characters) time to search the pattern in the text string, where l is the length of the text, and characters are the size of the alphabet. This code will check all the possible chances of the prefix in the longest string, which can be a suffix of ptn (0….. m - 1)x. Then, as an output, we will get the index at where the pattern string is found in the input string.

Next Topicforward driver method - Selenium Python

← prev next →