this post was submitted on 31 Oct 2024
326 points (97.4% liked)

Programmer Humor

32375 readers
457 users here now

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

Rules:

founded 5 years ago
MODERATORS
 

^.?$|^(..+?)\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
[โ€“] NateNate60@lemmy.world 5 points 6 days 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.

[โ€“] Rin@lemm.ee 1 points 5 days ago

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