# Does my finite state automaton accept a string iff it contains the given string as a substring?

I am trying to write down the generalized form of the finite automata which accept strings which contain as a substring an arbitrary string. Here is what I have come up with — I was hoping someone could tell me if I've made any mistakes (i.e., if there are any "bugs" in my "design").

Let $$\Sigma$$ be an alphabet.

For any substring $$S = s_{1}s_{2}s_{3}...s_{n}$$, where, $$s_i \in \Sigma$$

The FSA that accepts strings containing $$S$$ as a substring is,

$$Q=\{q_1, q_2, ..., q_n\} \cup \{q_0\}$$

$$F = \{q_n\}$$

$$$$\delta= \begin{cases} (\_, s_1) &\rightarrow &q_1&\\ (q_i, s_{i+1}) &\rightarrow &q_{i+1} &\forall& i\neq 0\\ (q_i, s_k) &\rightarrow &q_0 &\forall& k\neq i+1 \land k\neq 1\\ (q_n, \_) &\rightarrow &q_n \end{cases}$$$$

$$q_0$$ is the starting state.

My rationale —

The states $$\{q_1,q_2,...\}$$ represent the state of having just seen symbol $$s_i$$. If we see the next expected symbol $$s_{i+1}$$, we go to $$q_{i+1}$$ and so on until we reach $$q_n$$ or end of input. $$q_0$$ represents having just seen a symbol that is not in $$S$$. An '_' represents any possible value.

Your specification of the FSA is

• not finished. The transitions from states other than $$q_n$$ where the symbol read is not in $$S$$ are not defined.
• ambiguous.
• What happens if $$s_1=s_3$$? Are $$q_1$$ and $$q_3$$ the same state?
• Is the FSA deterministic or nondeterministic? It looks nondeterministic.

With the best intention to interpret your specification, consider the following example.

Let $$S=aab$$. The FSA will have four states, $$q_0, q_1, q_2, q_3$$.
Since $$aaab$$ contains $$aab$$ as a substring, the FSA should accept it.
On input $$aaab$$, the transitions of the FSA will be $$q_0\stackrel{a}{\to}q_1\stackrel{a}{\to}q_2\stackrel{a}{\to}q_0\stackrel{b}{\to}q_0.$$ However, $$q_3$$ is the only accept state.

### Two easy solutions

Let $$\Sigma$$ be an alphabet. Let $$S = s_{1}s_{2}s_{3}...s_{n}$$ is the substring we want to find, where $$n\ge1$$, $$s_i \in \Sigma$$.

Let the $$n$$-tail of a string $$w$$ be the longest suffix of $$w$$ not longer than $$n$$ symbols. It is $$w$$ if $$|w|< n$$, or the suffix of $$w$$ of length $$n$$ if $$|w|\ge n$$.

Here is a deterministic finite automaton $$D$$ that remembers the $$n$$-tail of $$w$$ when it has read $$w$$.

• For each string $$w$$ of length $$\le n$$, there is a state $$q_w$$.
• $$q_\epsilon$$ is the start state, where $$\epsilon$$ is the empty string.
• $$q_S$$ is the unique accept state.
• $$\delta(q_S,\sigma)=q_S$$.
• $$\delta(q_w, \sigma)=q_{\text{the n-tail of }w\sigma}$$ if $$w\not=S$$.

Here is a non-deterministic finite automaton $$N$$ that tries to match $$S$$ starting from every position. This NFA might have been your intention.

• $$Q=\{q_0, q_1, \cdots, q_n\}$$.
• $$q_0$$ is the start state.
• $$q_n$$ is the unique accept state.
• $$\delta=\begin{cases} (\_, \_) &\to &q_0&\\ (q_i, s_{i+1}) &\to &q_{i+1} &\forall i\lt n\\ (q_n, \_) &\to &q_n \end{cases}$$
where $$\_$$ represents any possible value

It is straightforward to verify both automata accept a string $$w$$ if and only if $$w$$ contains $$S$$ as a substring.

### Remarks on the problem

Constructing a finite automata which finds/accepts strings that contain a given string or does similar tasks is one of the most studied problems in computer science. Some famous solutions are Knuth–Morris–Pratt algorithm and Boyer–Moore algorithm. Can you find a better algorithm?