2
$\begingroup$

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\}$

\begin{equation} \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} \end{equation}

$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.

$\endgroup$

1 Answer 1

3
$\begingroup$

Remarks on your FSA

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.