Regular expression for the strings without a particular substring

Question

How can we design a regular expressions without particular substrings. The goal of this is to create language L which won't contain a particular substring (i.e. 110)

for the case of a regular expression without substring $110$, I Was thinking of: $\require{cancel}\cancel{(101)^*+}(010)^*+(10)^*+(\cancel{1}1)^*+(\cancel{0}0)^*+(01)^*$ but is that over excessive?

Then for example, I crossed out (101)* because obviously if you have two of those 101101, a subset of that will be 110, which we don't want.

Notes:

Question has been edited since it gained attention in the past few days. Also see comment for justification.

Answer 1

I did the following multistep technique.

Step 1: make a DFA that accepts all strings with "110". I am able to construct a DFA that accepts all strings with substring "110" and has just 4 states.

Step 2: Flip all the accepting states to non-accepting and all the non-accepting states to accepting. This page at Old Dominion describes the technique quite succinctly. This creates a DFA that accepts the language you want.

Step 3: Now you need to convert the DFA back to a regular expression. As @Alejandro Sazo mentioned there is a proof that this is possible. But you need an algorithm. This paper by Christoph Neumann describes three different techniques. The easiest one is the "state removal technique." You remove a state and replace all the edges between states that were connected to the removed state with edges labeled with regular expressions. As you reduce in this way you eventually get to a regular expression for the whole DFA. (Note that Figure 4 in the paper I linked is not quite right. The self-loop on state $q_j$ should have the regular expression "c e^* b", not "c e^* d".)

By going through this process it became clear that: the language you are going to need to solve for this particular problem has the property that once you have seen the sub-string "11" then you can never see another "0".

Answer 2

Here is a long answer: create the automata $M$ that recognizes the substring $110$, then create it's complement $\bar{M}$ and translate it into a regular expression. Fortunately this is possible thanks to the theorem:

If $L = L(M)$ is the lenguage recognized by a DFA $M$, then exists a regular expresion R such that $L = L(R)$

The answer is long because the number of steps (build $M$, build $\bar{M}$, create RE). In fact you may need to minimize the DFA before build the RE.

Answer 3

If your question is to find a regular expression for strings that avoid $110$ then a possible answer is $(0+10)^*1^*$ as computed by ChesterX. The intuition is clear: after two $1$'s we can only add $1$'s, so that can only happen at the end. Otherwise we are "safe" if we accompany every $1$ by a $0$.

If you question is how to find a regular expression for the expression avoiding subword $w$ in general, then follow the course set by Alajandro and Wandering Logic: (1) make a "linear" nondeterministic FSA for $\Sigma^* w \Sigma^*$, (2) determinize (3) complement (4) construct expression by successive state removal.

Here I want to make two remarks.

First, in general the determinization of a FSA can result in a exponentional blow-up in size. Fortunately in this setting this will not happen. The automata obtained are related to the construction of a patternmatching automaton due to Knuth-Morris-Prat.

Second, although the automaton will not explode in size, its structure can be nontrivial.

An example of both observations is given below. The automaton for pattern $11011010$ in both nondeterministic and deterministic versions. For the DFA I have cheated a little. For state $8*$ we find by the usual algorithm a large set of states, all accepting. That an easily be summarixed by this single state (which becomes useless after complementation).

Answer 4

I used jFlap to draw the DFA.

Then using jFlap again, got the RegEx as : $(0+10)^*(\lambda+1+111^*)$

Answer 5

I don't know the real logic but as per my understanding... It is clearly work on the logic of don't accept the 110 .. so it means whenever you got the substring like 110 ... At that time you must be not at a " Final state" so as per the above fig mentioned by my friend it is clear that after accepting the 0 in q2 state we not reach at final state it means ..We not get the final state so system generate error or ignore this type of no to accept ...And our aim to remove or not generate the string which contain 110 is clearly satisfy..