Geek asks and answers

Duplicate regular expressions

I need to write a regular expression that can detect a string containing only the characters x, y and z, but where the characters are different from their neighbors.

Here is an example

xyzxzyz = Pass

xyxyxyx = Pass

xxyzxz = Failure (repeated x)

zzzxxzz = Error (contiguous characters are repeated)

I thought this would work ((x | y | z)?) *, But it doesn't seem to work. Any suggestions?

EDIT

Please note: I am looking for an answer that does not allow me to look to the future or to look at operations. Only rotation, concatenation, grouping, and closing operations are allowed.

+2
source share
3 answers

, , DFA .

DFA. q1, q2, q3, q4 - , q1 . q5 - /.

DFA

DFA. , 5 :

qi Ri : a qi qj aRj. , . Ri - , λ .

, (λ - , ∅ - ):

(ab)c = a(bc) = abc
λx = xλ = x
∅x = x∅ = ∅
∅ + x = x
λ + x* = x*
(λ + x)* = x*

q5 - , , . , ​​ ( ).

:

R1 = xR2 + yR3 + zR4 + λ
R2 =     + yR3 + zR4 + λ
R3 = xR2 +     + zR4 + λ
R4 = xR2 + yR3       + λ

, :

X = AX + B, λ ∉ A, X = A*B.

.

, , .

R4 , , zλ z - :

R1 = xR2 + yR3 + (zxR2 + zyR3 + z) + λ
R2 =     + yR3 + (zxR2 + zyR3 + z) + λ
R3 = xR2 +     + (zxR2 + zyR3 + z) + λ

:

R1 = (x + zx)R2 + (y + zy)R3 + z + λ
R2 =       zxR2 + (y + zy)R3 + z + λ
R3 = (x + zx)R2 +       zyR3 + z + λ

R3:

R3 = (zy)*((x + zx)R2 + z + λ)
   = (zy)*(x + zx)R2 + (zy)*z + (zy)*

R3 R2 R1 R3. . , .

, , . q5 DFA.

R5 = (x + y + z)R5

∅ + x = x:

R5 = (x + y + z)R5 + ∅

R5:

R5 = (x + y + z)*∅

∅x = x∅ = ∅:

R5 = ∅

∅x = x∅ = ∅ , R5 , R5 .

+11

, :

^(?!.*(.)\1)[xyz]*$

(, )

: [xyz]* ( x, y z). ^...$ , . ( ) lookahead (?!.*(.)\1), , , .

+3

I had an idea when I walked today and put it on a regular expression, and I still have to find a template that does not match correctly. So here is the regex:

^((y|z)|((yz)*y?|(zy)*z?))?(xy|xz|(xyz(yz|yx|yxz)*y?)|(xzy(zy|zx|zxy)*z?))*x?$

Here is a fiddle to go with it!

If you find a pattern mismatch, tell me that I will try to change it! I know this a little late, but I was really worried by the fact that I could not solve it.

+1
source

More articles:


All Articles