Regular Expressions with repeated characters

by

Usually for this type of question, if the regex is not simple enough to be derived directly, you can start from drawing a DFA and derive a regex from there.

You should be able to derive the following DFA. q1, q2, q3, q4 are end states, with q1 also being the start state. q5 is the failed/trap state.

DFA

There are several methods to find Regular Expression for a DFA. I am going to use Brzozowski Algebraic Method as explained in section 5 of this paper:

For each state qi, the equation Ri is a union of terms: for a transition a from qi to qj, the term is aRj. Basically, you will look at all the outgoing edges from a state. If Ri is a final state, λ is also one of the terms.

Let me quote the identities from the definition section of the paper, since they will come in handy later (λ is the empty string and ∅ is the empty set):

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

Since q5 is a trap state, the formula will end up an infinite recursion, so you can drop it in the equations. It will end up as empty set and disappear if you include it in the equation anyway (explained in the appendix).

You will come up with:

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

Solve the equation above with substitution and Arden’s theorem, which states:

Given an equation of the form X = AX + B where λ ∉ A, the equation has the solution X = A*B.

You will get to the answer.

I don’t have time and confidence to derive the whole thing, but I will show the first few steps of derivation.

Remove R4 by substitution, note that zλ becomes z due to the identity:

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

Regroup them:

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

Apply Arden’s theorem to R3:

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

You can substitute R3 back to R2 and R1 and remove R3. I leave the rest as exercise. Continue ahead and you should reach the answer.

Appendix

We will explain why trap states can be discarded from the equations, since they will just disappear anyway. Let us use the state q5 in the DFA as an example here.

R5 = (x + y + z)R5

Use identity ∅ + x = x:

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

Apply Arden’s theorem to R5:

R5 = (x + y + z)*∅

Use identity ∅x = x∅ = ∅:

R5 = ∅

The identity ∅x = x∅ = ∅ will also take effect when R5 is substituted into other equations, causing the term with R5 to disappear.

More Related Contents:

  1. What kind of formal languages can modern regex engines parse?
  2. string pattern matching using perl regex [closed]
  3. Can regular expressions be used to match nested patterns? [duplicate]
  4. Why is this regex allowing a caret?
  5. Regex: ignore case sensitivity
  6. How can we match a^n b^n?
  7. Decimal or numeric values in regular expression validation
  8. Carets in Regular Expressions
  9. What is the ultimate postal code and zip regex?
  10. How do you debug a regex? [closed]
  11. (grep) Regex to match non-ASCII characters?
  12. Negating a backreference in Regular Expressions
  13. Regex to split HTML tags
  14. What’s the technical reason for “lookbehind assertion MUST be fixed length” in regex?
  15. R/regex with stringi/ICU: why is a ‘+’ considered a non-[:punct:] character?
  16. Convert dd/mm/yy and dd/mm/yyyy to Dates
  17. Matching math expression with regular expression?
  18. Select rows from data.frame ending with a specific character string in R
  19. Regex to match any character including new lines
  20. Regex: How to match a string that is not only numbers
  21. apache mod_rewrite one rule for any number of possibilities
  22. How do I get regex support in Excel via a function, or custom function?
  23. Regular Expression Word Boundary and Special Characters
  24. How to search and replace with a counter-based expression in Vim?
  25. Combining $regex and $or operators in Mongo
  26. Case insensitive search in Mongo
  27. Why does VIM have its own regex syntax?
  28. Redirect all traffic to root of another domain
  29. ignoring changes matching a string in git diff
  30. Regex allow digits and a single dot

Leave a Comment