0
$\begingroup$

Consider these Regexes written in Julia (they should be equivalent in Python):

φ = Regex("(?:[X](I*)){$n,}(?:5|6{$m,}|\\\$)")
ζ = Regex("(?:[X](I*)){$n,}(?:[5](I*){$m,}|6{$m,}|\\\$)")

They operate on a language $\Sigma = \{X, I, 5, 6\}$. They find patterns that consist of

  • occurrences of $2, 3, 4, I$ (in any order) where total number of $2$s, $3$s and $4$s is at least $n$, as long as these occurrences end with a $m$ repetitions of character $5$ or $m$ repetitions of character $6$.

The difference between the first and second regex is that the first does not impose the condition that the sequence ends with more than $1$ repetitions of 5.

What are their equivalent regular expressions?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I don't understand what you are asking. Please ask about only a single language/regexp at a time. Can you give a self-contained specification of the language you are referring to, so we don't have to understand Julia/Python regex syntax? Why do you write X,I,5,6 in one place but 2,3,4,I in another place? What have you tried and what progress have you made? See cs.stackexchange.com/q/45570/755 for how to approach such tasks. $\endgroup$
    – D.W. ♦
    Commented May 5 at 18:18
  • $\begingroup$ Why write [X] and [5] instead of just X and 5? $\endgroup$
    – reinierpost
    Commented May 6 at 14:35
  • $\begingroup$ The first line should have 5{$n,} instead of 5. $\endgroup$
    – reinierpost
    Commented May 6 at 14:37
  • $\begingroup$ You explanation is contradictory. 2, 3, and 4 do not occur. Do you mean [234] instead of [X]? $\endgroup$
    – reinierpost
    Commented May 6 at 14:42
  • $\begingroup$ Contrary to your explanation, there is no conditional dependency between the two parts of the expressions. You can write textbook regular expressions for the parts and concatenate them. $\endgroup$
    – reinierpost
    Commented May 6 at 14:43

1 Answer 1

Reset to default
0
$\begingroup$

I think this is what you are looking for: $I^*(2I^* + 3I^* + 4I^*)^n(2I^* + 3I^* + 4I^*)^*(5^m + 6^m)$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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