2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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:

enter image description here

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

enter image description here

Drop the one way road:

enter image description here

Then we eliminate the original states one by one:

enter image description here

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ What does $\epsilon$ mean? $\endgroup$ – mathreadler Oct 18 '15 at 5:06
  • 2
    $\begingroup$ The empty word, in a prog lang it is e.g. "" This is different from the empty language. Regular languages are inductively created from $\emptyset, \{\epsilon\}$ and $\{a\} \quad (a\in \Sigma)$. $\endgroup$ – mvw Oct 18 '15 at 5:07
  • $\begingroup$ You have a much better systematic testing procedure than I do. I should probably try something similar. $\endgroup$ – mathreadler Oct 18 '15 at 17:21
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @mvw: I think you assume wrongly. He probably meant using disjunction. $\endgroup$ – user21820 Oct 18 '15 at 15:25
  • $\begingroup$ Ok, then assume Brian meant $0^*(11^*000^*)^*\mid 10$. The resulting language would not contain the valid strings $1+$. $\endgroup$ – mvw Oct 18 '15 at 15:28
  • $\begingroup$ @mvw: I was distracted when I did that, focussing too much on the OP’s automaton and not enough on the language, and probably should have waited until I could give it my full attention. I actually was thinking of tacking on $1^*10$, not $10$, but of course the final $0$ should be optional. $\endgroup$ – Brian M. Scott Oct 18 '15 at 18:51
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree it is difficult. But it is a fun sport. $\endgroup$ – mathreadler Oct 18 '15 at 5:00
  • $\begingroup$ Yes thank you, also $1^*$ was not even needed in the position after some adjustments. $\endgroup$ – mathreadler Oct 18 '15 at 15:05
  • $\begingroup$ Your reg exp from your text seems to work, but that one from your test2 does not. $\endgroup$ – mvw Oct 18 '15 at 16:05
  • $\begingroup$ One of the tests is just to find all strings of 0 or 1, the other one is to disqualify any which does not fit the "101" criteria. Probably not the prettiest way to do it. But it works on my computer using the test-string "teststr". However that is not a very thorough search since there are just fewer than 10 test cases. $\endgroup$ – mathreadler Oct 18 '15 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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