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?
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)*
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.
grep '^[123]*$' | grep -v 123 | grep -v '222.*222'is much easier to understand than a single regular expression. $\endgroup$