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

<answer>

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

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

You are viewing a single thread.
View all comments View context
6 points

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.

permalink
report
parent
reply
1 point

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

permalink
report
parent
reply

Programmer Humor

!programmerhumor@lemmy.ml

Create post

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.

Community stats

  • 5.3K

    Monthly active users

  • 884

    Posts

  • 8.9K

    Comments

Community moderators