Skip to main content
Computer Science

Return to Answer

replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).

The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular?How to prove that a language is not regular? for more methods, and questions tagged pumping-lemmaquestions tagged pumping-lemma for examples of using the pumping lemma.

For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language?What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.

This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).

The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular? for more methods, and questions tagged pumping-lemma for examples of using the pumping lemma.

For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.

This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).

The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular? for more methods, and questions tagged pumping-lemma for examples of using the pumping lemma.

For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.

Source Link
Gilles 'SO- stop being evil'
Gilles 'SO- stop being evil'
  • 44k
  • 8
  • 118
  • 184

This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).

The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular? for more methods, and questions tagged pumping-lemma for examples of using the pumping lemma.

For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.