• NateNate60@lemmy.worldOP
    link
    fedilink
    arrow-up
    6
    ·
    25 天前

    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.