How can I implement a Deterministic finite automaton which accepts strings having specific words.

Question

I am trying to make a Deterministic finite automaton which accepts those strings having two specific words(either one) anywhere as a substring. The problem is really simple if the characters of the words do not match, on the contrary if the characters of these two words match somewhere, then I don't see any way out.

For instance how can I implement a DFA which accepts those strings having $100$ or $110$ as substring anywhere?

Answer 1

Possible solution:

1. Build a DFA $A_1$ that accepts strings with $100$.
2. Build a DFA $A_2$ that accepts strings with $110$.
3. Build DFA $A$ that accepts strings with $100$ or $110$. The latter is the union of DFA's $A_1$ and $A_2$ (the union accepts a string iff it is accepted by $A_1$ or $A_2$). Here [ link ] (pp.3-5) you can find some example how to perform this operation.

P.S.: If you need a DFA that accepts a string iff it is accepted by $A_1$ and $A_2$ you can use the intersection of DFA's.

Answer 2

Here is a NFA accepting your language, where I the an initial state, and F is a final state.

It reads the word, and, in a non-deterministic way, choses to read one of the subword you want.

Then, you "just" have to determinise it (be careful, it can have up to $2^8$ states… you may want to rewrite the NFA with less states)

Answer 3

Let $M=(Q,\Sigma, \delta, q_0, F)$ where the set of states is $$Q=\{q_0, q_1, q_{11}, q_{10}, q_f\}, $$ the input alphabet is $$\Sigma = \{0,1\}, $$ the transition function $\delta: Q\times \Sigma\to\ Q$ is defined by \begin{array}{c|c|c|c|c|c} \delta(q,b)& q_0 & q_1 & q_{11} & q_{10} & q_f\\\hline 0 & q_0 & q_{10} & q_f & q_f & q_f \\ 1 & q_1 & q_{11} & q_{11} & q_1 & q_f \end{array}

$q_0$ is the start state, and $F=\{q_f\}$ is the set of accepting states. Then the language of $M$ is $$(0\cup 1)^*(100)\cup(110)\cup(0,1)^*, $$ as desired.