Programmer Humor

32472 readers

515 users here now

Post funny things about programming here! (Or just rant about your favourite programming language.)

Rules:

Posts must be relevant to programming, programmers, or computer science.
No NSFW content.
Jokes must be in good taste. No hate speech, bigotry, etc.

founded 5 years ago

MODERATORS

[email protected]

328

Oh boy what a beautiful regex. I'm sure it does something logical and easy to understand. (lemmy.world)

submitted 2 weeks ago* (last edited 2 weeks ago) by [email protected] to c/[email protected]

83 comments fedilink hide all child comments

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

Matches strings of any character repeated a non-prime number of times

https://www.youtube.com/watch?v=5vbk0TwkokM

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 2 points 2 weeks ago (2 children)

You can have states point to each other in a loop, no?

[–] [email protected] 6 points 2 weeks ago (1 children)

If the set of all strings of composite length is a regular language, you can use that to prove the set of all strings of prime length are also a regular language.

But it's also easy to prove that the set of language of strings of prime length is not regular, and thus the language of strings of composite length also can't be regular.

A more formal proof.

[–] [email protected] 1 points 2 weeks ago

Thank you for this. I'll review this when I can.

[–] [email protected] 3 points 2 weeks ago* (last edited 2 weeks 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.