2
$\begingroup$

I need a regular expression, not one using coding syntax, to write an expression that has a vocabulary of 1,2,3 and every string in the language has at most one occurrence of the substring 222 but never has the occurrence of 123.

((1 or 3)*(211 or 231 or 233 or 2211 or 2231 or 2233))* 222 

is as far as I could get, I can't see how to prevent 123 from happening while still allowing a string like 1223221222 to occur. Any thoughts?

$\endgroup$
  • $\begingroup$ cs.stackexchange.com/q/45570/755 $\endgroup$ – D.W. Mar 19 at 1:48
  • $\begingroup$ From a code readability perspective, this is a bad idea - better use several matches, including negative ones, if you can. E.g. on the Unix command line, grep '^[123]*$' | grep -v 123 | grep -v '222.*222' is much easier to understand than a single regular expression. $\endgroup$ – reinierpost Mar 19 at 11:47
  • $\begingroup$ The title doesn't quite match the content. Can you fix the title? $\endgroup$ – reinierpost Mar 20 at 12:49
  • $\begingroup$ With "does not" tasks, it may be easier to construct an NFA and convert to a regular expression using one of the canonical algorithms. $\endgroup$ – Raphael Mar 21 at 16:29
1
$\begingroup$

First, "has no occurence of 123".

So the string can start with any number of 2s and 3s. Then it has 0, 1 or more components that start with 1, and followed by any number of 2s and 3s other than 23. So the 1 is followed by nothing, a single 2, 22 and any number of 2s and 3s, or 3 and any number of 2s and 3s.

Each of these components could contain three or four consecutive 2s. Four consecutive 2s are not allowed, three consecutive 2s may only happen once. So for each of those components add things to not allow three 2s in a row, or to allow three but not four 2s in a row. And then the language is any number of components with no three 2s, optionally followed by a component with three 2s and any number of components with no three 2s.

It's a bit complicated, but not too bad.

So make regular expressions for "lead_2" = "any number of 2s and 3s, but no three 2s in a row", "lead_3" = "any number of 2s and 3s, with 222 once but not twice, and no 2222", "follow_2" = "1, followed by lead_2 not starting with 23", "follow_3" = "1, followed by lead_3 not starting with 23", and the whole language is

lead_2 (follow_2)* or
lead_2 (follow_2)* follow_3 (follow_2)* or
lead_3 (follow_2)*
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Assuming that we consider 2222 to contain 222 twice (from character 1 to 3, and from character 2 to 4): We define some building blocks: A = "no 1's, no 222". B = "no 1's, exactly one 222", C = "1 followed by A, but not followed by 23", and D = "1 followed by B, but not followed by 23". Then the regular expression is

A C* | A C* D C* | B C* = (A | A C* D | B) C*

We take another building block X = ((2 | 22)? 3)* which is any number of 3s, each preceeded by one, two or no 2's.

A consists of any number of 3s preceeded by no, one or two 2s, followed by no, one or two 2s. A = X (2 | 22)?

B is quite similar, but it ends either in 222, or in 2223 followed by A: B = X 222 (3 A)?

C starts with 1. If there are any 3's, then the first one is not preceded by exactly one 2, otherwise it is very similar to A: C = 1 ((22)? 3 X)? (2 | 22)?.

D starts with 1, followed by B, but again if there are any 3's then the first one is not preceded by exactly one 2. D = 1 ((22)? 3 X)? 222 (3 A)?.

To get the usual regular expression, substitute everything, which will make the expression rather large and unreadable.

(((2 | 22)? 3)* (2 | 22)? | ((2 | 22)? 3)* (2 | 22)? (1 ((22)? 3 ((2 | 22)? 3)*)? (2 | 22)?)* 1 ((22)? 3 ((2 | 22)? 3)*)? 222 (3 ((2 | 22)? 3)* (2 | 22)?)? | ((2 | 22)? 3)* 222 (3 ((2 | 22)? 3)* (2 | 22)?)?) (1 ((22)? 3 ((2 | 22)? 3)*)? (2 | 22)?)*

Same thing can be achieved with a state machine with 10 accepting states and one non-accepting state.

| cite | improve this answer | |
$\endgroup$

Your Answer

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