Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

Question

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem.

Create a regular expression for the following language:

The set of all strings that do not contain "101" as a substring.

I tried to create the expression and found I couldn't, so I create an automata, but I have figured out how to translate it into a regular expression.

Answer 1

A regular expression is $$ (0\mid 11^*00)^*(\epsilon\mid 11^*(\epsilon\mid 0)) = \\ (0\mid 1^+00)^*(\epsilon\mid 1^+(\epsilon\mid 0)) = \\ (0\mid 1^+00)^* \mid (0\mid 1^+00)^*(1^+\mid 1^+0) $$

Update

I told my friend Ruby to check the given regular expressions (link),

 goal = !((u =~ /101/).is_a? Integer)
 res1 = (u =~ /\A(0*(11*000*)*(10)?)\z/).is_a? Integer
 res2 = (u =~ /\A(0*((1*00+)*1*0*))\z/).is_a? Integer
 res3 = (u =~ /\A((0|1+00)*|(0|1+00)*(1+|1+0))\z/).is_a? Integer

this is what she got (link):

Testing "not containing 101" for the first 1024 non-empty binary words:
   0:           0 => goal = true, 1: true, 2: true, 3: true
   1:           1 => goal = true, 1: false ERROR, 2: true, 3: true
   2:          10 => goal = true, 1: true, 2: true, 3: true
   3:          11 => goal = true, 1: false ERROR, 2: true, 3: true
   4:         100 => goal = true, 1: true, 2: true, 3: true
   5:         101 => goal = false, 1: false, 2: false, 3: false
   6:         110 => goal = true, 1: false ERROR, 2: true, 3: true
   7:         111 => goal = true, 1: false ERROR, 2: true, 3: true
   8:        1000 => goal = true, 1: true, 2: true, 3: true
   .
   .
1020:  1111111100 => goal = true, 1: true, 2: true, 3: true
1021:  1111111101 => goal = false, 1: false, 2: false, 3: false
1022:  1111111110 => goal = true, 1: false ERROR, 2: true, 3: true
1023:  1111111111 => goal = true, 1: false ERROR, 2: true, 3: true
errors for regexp 1: 200
errors for regexp 2: 0
errors for regexp 3: 0
done.

Transformation of the deterministic finite automaton into a regular expression

We start with this DFA:

Then turn it into this Thompson NFA, having dedicated start and finish states:

Drop the one way road:

Then we eliminate the original states one by one:

Answer 2

One way is to take it in pieces. Clearly your automaton accepts $0^*$. What else gets it back to state $a$? Only $11^*00$, after which you can have any number of zeroes again. Thus, $0^*(11^*000^*)^*$ almost does the trick. However, like your automaton, it misses the possibility that an acceptable string can end in $1$ or $10$ if no $0$ immediately precedes the $1$. (For example, the words $11$ and $1110$ should be accepted.) Can you see how to adjust it (and your automaton) to reflect that possibility?

Answer 3

So here is my attempt without any state machines...

$$0^*1^*?(1^*00^+1^*)^*0^*$$

Better version ( minor adjustments, some unnecessary terms ):

$$0^*((1^*00^+)^*1^*0^*)$$

where + means 1 or more matches, * 0 or more matches.

I have tried it later on, but first some thinking as why it should work

Here the philosophy that we start at the endpoints and work inwards. Any number of zeros at the start and stop, whenever we have any zero on the interior it needs to be at least two of them but any run length of zeroes can have any length of runs of 1s before and after it and there can be any number of such interior "blocks" why we get a star on the parenthesis too.

---

For my lack of rigor I think I should paste a working example in Python to show it works:

teststr = "aa1100aa100aa10ba011aa1101aba110aa111011100000111aaa";

test1 = [m2 for m2 in [re.sub("[^01]+","",m) for m in re.findall("[^01]+?[01]+[^01]+?",teststr)]]

test2 = [m3.group(0) for m3 in [re.match("0*((1*00+)*1*0*)",m2) for m2 in [re.sub("[^01]+","",m) for m in re.findall("[^01]+?[01]+[^01]+?",teststr)]]]

list(set.intersection(set(test1),set(test2)))

gives output:

['10', '100', '110', '1100', '011']

Explanation:

test1 is just to extract each run of 0 and 1.

test2 tries the regex on each of those runs.

set intersection picks out the successful candidates.