• balsoft@lemmy.mlEnglish
    3·
    1 day ago

    So, here’s my attempt

    The first portion (^.?$) matches all lines of 0 or 1 characters.

    The second portion (^(..+?)\1+$) is more complicated:

    1. (..+?) is a capture group that matches the first character in any line, followed by a smallest possible non-zero number of characters such that (2) still matches (note that the minimum length of this match is 2)
    2. \1+ matches as many as possible (and more than 0) repeats of the (1) group

    I think what this does is match any line consisting of a single character with the length

    • divisible by some number (due to the more than 0 condition in (2), so that there have to be repeats in the string), that’s not
      • 1 (due to the note in (1), so that the repeating portion has to be at least 2 characters long), or
      • the length itself (due to the more than 0 condition in the (2), so that there is at least one repetition)

    Therefore, combined with the first portion, it matches all lines of the same character whose lengths are composite (non-prime) numbers? (it will also match any line of length 1, and all lines consisting of the same string repeated more than one time)

    • CanadaPlus@lemmy.sdf.org
      2·
      1 day ago

      So this is a definite example of “regex” that’s not regular, then. I really don’t think there’s any finite state machine that can track every possible number of string repeats separately.

      • NateNate60@lemmy.worldOP
        1·
        1 day ago

        You got downvoted here but you’re absolutely right. It’s easy to prove that the set of strings with prime length is not a regular language using the pumping lemma for regular languages. And in typical StackExchange fashion, someone’s already done it.

        Here’s their proof.

        Claim 1: The language consisting of the character 1 repeated a prime number of times is not regular.

        A further argument to justify your claim—

        Claim 2: If the language described in Claim 1 is not regular, then the language consisting of the character 1 repeated a composite number of times is not regular.

        Proof: Suppose the language described in Claim 2 is regular if the language described in Claim 1 is not. Then there must exist a finite-state automaton A that recognises it. If we create a new finite-state automaton B which (1) checks whether the string has length 1 and rejects it, and (2) then passes the string to automaton A and rejects when automaton A accepts and accepts when automaton A rejects, then we can see that automaton B accepts the set of all strings of non-composite length that are not of length 1, i.e. the set of all strings of prime length. But since the language consisting of all strings of prime length is non-regular, there cannot exist such an automaton. Therefore, the assumption that the language described in Claim 2 being regular is false.

        • CanadaPlus@lemmy.sdf.org
          2·
          8 hours ago

          By now, I have just one, so thanks for the assist. There’s always that one (sometimes puzzling) downvote on anything factual.

          The pumping lemma, for anyone unfamiliar. It’s a consequence of the fact an FSM is finite, so you can construct a repeatable y just by exhausting the FSM’s ability to “remember” how much it’s seen.

        • CanadaPlus@lemmy.sdf.org
          2·
          9 hours ago

          Yeah, but in an FSM all you have are states. To do it the obvious way, you need a loop with separate branches for every number greater than 2, or at the very least every prime number, and that’s not going to be finite.

  • fubo@lemmy.world
    8·
    1 day ago

    The answer given in the spoiler tag is not quite correct!

    Test case

    According to the spoiler, this shouldn’t match “abab”, but it does.

    Corrected regex

    This will match what the spoiler says: ^.?$|^((.)\2+?)\1+$

    Full workup

    Any Perl-compatible regex can be parsed into a syntax tree using the Common Lisp package CL-PPCRE. So if you already know Common Lisp, you don’t need to learn regex syntax too!

    So let’s put the original regex into CL-PPCRE’s parser. (Note, we have to add a backslash to escape the backslash in the string.) The parser will turn the regex notation into a nice pretty S-expression.

    > (cl-ppcre:parse-string "^.?$|^(..+?)\\1+$")
(:ALTERNATION
 (:SEQUENCE :START-ANCHOR (:GREEDY-REPETITION 0 1 :EVERYTHING) :END-ANCHOR)
 (:SEQUENCE :START-ANCHOR
  (:REGISTER
   (:SEQUENCE :EVERYTHING (:NON-GREEDY-REPETITION 1 NIL :EVERYTHING)))
  (:GREEDY-REPETITION 1 NIL (:BACK-REFERENCE 1)) :END-ANCHOR))

    At which point we can tell it’s tricky because there’s a capturing register using a non-greedy repetition. (That’s the \1 and the +? in the original.)

    The top level is an alternation (the | in the original) and the first branch is pretty simple: it’s just zero or one of any character.

    The second branch is the fun one. It’s looking for two or more repetitions of the captured group, which is itself two or more characters. So, for instance, “aaaa”, or “abcabc”, or “abbaabba”, but not “aaaaa” or “abba”.

    So strings that this matches will be of non-prime length: zero, one, or a multiple of two numbers 2 or greater.

    But it is not true that it matches only “any character repeated a non-prime number of times” because it also matches composite-length sequences formed by repeating a string of different characters, like “abcabc”.

    If we actually want what the spoiler says — only non-prime repetitions of a single character — then we need to use a second capturing register inside the first. This gives us:

    ^.?$|^((.)\2+?)\1+$.

    Specifically, this replaces (..+?) with ((.)\2+?). The \2 matches the character captured by (.), so the whole regex now needs to see the same character throughout.

      • fubo@lemmy.world
        1·
        2 days ago

        Regex is good for a few very specific things, and sysadmins used to use it for goddamn everything. If all your server logs are in lightly-structured text files on a small number of servers, being able to improvise regex is damn useful for tracking down server problems. Just write a shell loop that spawns an ssh logging into each server and running grep over the log files, to look for that weird error.

        These days, if you need to crunch production server logs you probably need to improvise in SQL and jq and protobufs or systemd assmonkery or something.

        But if you actually need a parser, for goodness sake use a parser combinator toolkit, don’t roll your own, especially not with regex. Describing your input language in plain Haskell is much nicer than kludging it.

        (This is the “totally serious software engineering advice” forum, right?)

  • SpiceDealer@lemmy.world
    0·
    22 hours ago

    I could be wrong but I think the (..+?) portion will either remove a dud or replenish the allowance.