ISI PCB 2014 C3 (A)

Question

Prove that the language {aN : N is a composite number} is not
regular.

Answer 1

- In order to prove that a number N is composite,  we need to prove that it has more than 2 factors i.e 1 and itself.

- This cannot be done with a fixed amount of memory as the number of cases to check increases as N increases

- As regular language has a finite amount of memory, proving that number N is composite is not regular

- The language can be recognised by a Turing machine.

Comments

They asked for proof, so how can this answer be accepted as proof?

Answer 2

• With a choice of $m$, we pick w = $a^{n}$ : where n is composite and $n \geq m$
• If $w = xyz$ , is the decomposition, then $y =a^k$ : where $0 \leq k \leq m$ because $|xy| \leq m$
• Now, $w_i$ = $a^{n-k}.a^{ki}$
• This $n+(i-1)k$ quantity is not always composite : for example $ n = 10 , i = 2 , k = 3 $ and we have $w_2$ is not in language.
• Therefore, the language is not regular.